Educational Codeforces Round 6 D. Professor GukiZ and Two Arrays

时间:2023-03-09 05:44:22
Educational Codeforces Round  6 D. Professor GukiZ and Two Arrays

Professor GukiZ and Two Arrays

题意:两个长度在2000的-1e9~1e9的两个序列a,b(无序);要你最多两次交换元素,使得交换元素后两序列和的差值的绝对值最小;输出这个最小的和的差值的绝对值;并且输出交换次数和交换的序号(从1 开始)
Input
5
5 4 3 2 1
4
1 1 1 1
Output
1
2
1 1
4 2

策略:

若是只交换一次,直接O(n^2)暴力即可;但是里面可以交换两次。。若是分开看。。没思路。那就开始时就预处理出同一个序列中任意两个位置的数的和,这就还是转换为了一次交换。一个序列任意两元素之和的个数已经到了O(n^2),那在处理的时候使用贪心策略(看代码就知道了),是O(n^2);

ps:原本1e9数量级的范围相加减是不会爆int的范围,但是我就是坑在这个上了。。强制改成了2ll*。。。(求解);

//483ms
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for((i) = 0;i < (n);i++)
#define all(vec) (vec).begin(),(vec).end()
typedef long long ll;
typedef pair<int,int> PII;
#define A first
#define B second
#define pb push_back
vector<pair<int,PII> > va,vb;
int a[],b[];
PII ans[];
int main()
{
int na,nb,i,j,tot = ;
ll sum = ;
cin>>na;
rep(i,na){
scanf("%d",a + i);
sum += a[i];
rep(j,i) va.pb({a[j]+a[i],{j,i}});
}
cin>>nb;
rep(i,nb){
scanf("%d",b + i);
sum -= b[i];
rep(j,i) vb.pb({b[j]+b[i],{j,i}});
}
ll mn = abs(sum);
ll dif;
rep(i,na){
rep(j,nb){
dif = sum - 2ll*a[i] + 2ll*b[j]; //要分开*2再-+;
if(mn > abs(dif)){
mn = abs(dif);
tot = ;
ans[] = {i,j};
}
}
}
sort(all(va)); sort(all(vb));
for(i = ,j = ;i < va.size() && j < vb.size();){
dif = sum - 2ll*va[i].A + 2ll*vb[j].A; // 改成2ll才A
if(mn > abs(dif)){
mn = abs(dif);
tot = ;
ans[] = {va[i].B.A,vb[j].B.A};
ans[] = {va[i].B.B,vb[j].B.B};
}
if(dif > ) i++;
else j++;
}
printf("%I64d\n",mn);
printf("%d\n",tot);
rep(i,tot)
printf("%d %d\n",ans[i].A+,ans[i].B+);
}