题目链接
题意:
给定N≤2×103的两个序列,给定0≤k≤2次交换2个序列中一个数的操作,使得|suma−sumb|最小
思路:
考虑N最大为2e3,所以考虑对交换0次或1次的我们可以直接暴力来求,枚举哪两个数交换,复杂度 O(N2)
1.交换一次 零次
设sa-sb为s,假设交换a[i]和b[j]两个元素那么 sa’ = s-a[i]+b[j] ,sb' = s-b[j]+a[i]。 s'=|sa-sb| =|s-2*a[i]+2*b[j]|.
2.交换两次.根据上面的方法,我们假设交换两次时两个数分别为 a[i1],a[i2],b[j1],b[j2]。
那么新的s' = s-2*(a[i1]+a[i2])+2*(b[j1]+b[j2])。为了让s'尽可能小,s'最小为0,那么有2*（b[j1]+b[j2]）=2*(a[i1]+a[i2])-s. 那么我们选取的b[j1]+b[j2]的可能值有正好等于右面,刚大于右面,刚小于右面(因最后结果要绝对值)。
所以我们可以预处理任意a【i1】+a【i2】的和,然后二分去找b【j1】+b【j2】 复杂度O(N2LOGN)
#include<bits/stdc++.h> #define mk make_pair using namespace std; typedef long long ll; const ll inf = 1e19; const int maxn = 2e3+10; ll a[maxn],b[maxn]; pair<ll,pair<int,int> > ansb[maxn*maxn]; pair<int,int>ans,ans1,ans2; int main() { int n,m; scanf("%d",&n); int cnt = 0; ll s = 0; for(int i = 1;i <=n ;i++) { scanf("%lld",&a[i]); s += a[i]; } scanf("%d",&m); for(int i = 1;i <= m ;i++) { scanf("%lld",&b[i]); s -= b[i]; } ll s2 = inf; for(int i = 1;i <= n;i++) { for(int j = 1;j <= m;j++) { ll tmp = abs(s - 2*a[i] +2*b[j]); if(s2 > tmp) { s2 = tmp; ans =mk(i,j); } } } for(int i = 1;i <= m;i++) for(int j = i + 1;j <= m;j++) ansb[++cnt] = mk(2*(b[i] + b[j]),mk(i,j)); sort(ansb+1,ansb+cnt+1); ll s3 = inf; for(int i = 1;i <= n;i++) for(int j = i + 1;j <= n;j++) { ll tmp = 2*a[i] + 2*a[j] - s; int t = lower_bound(ansb+1,ansb+1+cnt,mk(tmp,mk(0,0))) - ansb; for(int k = max(1,t-1);k<=min(cnt,t+1);k++)//小技巧 { ll now = abs(ansb[k].first - tmp); if(now < s3) { s3 = now; ans1 = mk(i,ansb[k].second.first); ans2 = mk(j,ansb[k].second.second); } } } ll res = min(min(abs(s),abs(s2)),abs(s3)); printf("%lld\n",res); if(res == abs(s)) puts("0"); else if(res == abs(s2)) { puts("1"); printf("%d %d\n",ans.first,ans.second); } else { puts("2"); printf("%d %d\n%d %d\n",ans1.first,ans1.second,ans2.first,ans2.second); } return 0; }
PS：当然这个题还有更好的做法,因为观察到因为s一定的,随着a[i1]+a[i2]只的增大,b[j1]+b[j2]只增不减,根据这个性质可以采用双指针.预处理任意a[i1]+a[i2]和b[j1]+b[j2] 的和,然后使他们各自有序,然后双指针扫描,还是寻找上述三种情况的,
这样复杂度为n2,可以降个LOG .这里不给出代码了.
Marcus-Bao 认证博客专家 推荐系统 ACM算法竞赛 机器学习 本科毕业于国内知名四非大学，现中国科学院大学博士生，中国科学院计算技术研究所vipl实验室，老年ACM铁牌退役选手，喜欢算法竞赛，会点数据结构和算法，熟悉c++，python等；现阶段研究方向主要为机器学习与数据挖掘，比较关注推荐系统，发过顶会，炼过丹，平时博客主要记录些关于算法、数据结构，人工智能技术以及平时看的论文总结分享等，欢迎大家关注我，一起多多交流共同进步！