• 周日. 6月 26th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

nowcoder11166G Game of Swapping Numbers(2021牛客暑期多校训练营1)贪心 抽屉原理

admin

11月 28, 2021

题意

给定两个等长数组(A,B),任意交换(A)中的两个元素(K)次,求(max{sum_{i=1}^Nmid A_i-B_imid})(2le Nle5×{10}^5,0le Kle{10}^8,-{10}^8le A_i,B_ile{10}^8)

分析

先考虑交换任意次的情况。求和时,我们考虑去掉绝对值,则相当于为每一对(A_i,B_i)分配了一个正号和一个负号。考虑重新分配正负号:由于一对(A_i,B_i)的正负号与真实情况相反一定不是更优,那么对于(A)的一个新的排列,交换任意次的最大值就为(A)(B)两个数组合并后最大的(N)个减最小的(N)个。

再由鸽巢原理,在(N>2)时,(A)中一定有两个正或两个负。交换至最大值后,任意正号的数一定大于所有负号的数,对于多余的次数只需交换两个正号或者负号,那么交换次就可以等价于交换至多(K)次。(N=2)的情况特判即可。

观察重新分配正负号后的两个数组,对于(A_i,B_i)一正一负的不需要移动(A_i)就可以满足最大值的状态,对于两个正号的需要(A_i)与两个负号的(A_j)交换才能满足最大值。对于一次交换,新增的贡献为((A_i+B_i)-(max(A_i,B_i)-min(A_i,B_i))=2*min(A_i,B_i))。同理,对于两个负号新增的贡献为(-2*max(A_i,B_i))。对于每次交换,贪心地取最大的两个即可。

代码

#include <bits/stdc++.h>
using namespace std;
constexpr int N(5e5+5);
using pii=pair<int,int>;
int a[N],b[N],x[N];
pii c[N*2];

int main() {
  int n,k;
  cin>>n>>k;
  for(int i=0;i<n;i++) {
    cin>>a[i];
    c[i]={a[i],i};
  }
  for(int i=0;i<n;i++) {
    cin>>b[i];
    c[i+n]={b[i],i};
  }
  sort(c,c+n*2);
  for(int i=0;i<n;i++)
    x[c[i].second]--;
  for(int i=n;i<n*2;i++)
    x[c[i].second]++;
  priority_queue<pii>q[2];
  long long ans=0;
  for(int i=0;i<n;i++) {
    if(x[i]==2)
      q[0].push({2*min(a[i],b[i]),i});
    else if(x[i]==-2)
      q[1].push({-2*max(a[i],b[i]),i});
    ans+=abs(a[i]-b[i]);
  }
  int t=q[0].size();
  if(n==2) {
    if(k%2)
      ans=abs(a[0]-b[1])+abs(a[1]-b[0]);
    else
      ans=abs(a[0]-b[0])+abs(a[1]-b[1]);
  }
  else {
    t=min(k,t);
    while(t--) {
      ans+=q[0].top().first+q[1].top().first;
      q[0].pop();
      q[1].pop();
    }
  }
  cout<<ans<<'
';

  return 0;
}

发表评论

您的电子邮箱地址不会被公开。