题目

传送门

思路

如果交换一次和交换零次都很容易实现

这里主要讨论交换两次的情况

我们设\(s_1\)为\(a\)数列的和，\(s_2\)为\(b\)数列的和

我们考虑交换两个数，实际上是变成\(s_1-a_{i1}-a_{j1}+b_{i2}+b_{j2}\)和\(s_2-b_{i2}-b_{j2}+a_{i1}+a_{j1}\)

同时两个数列的总和是不变的，所以一个数列的和越接近\(\frac{s_1+s_2}{2}\)越好

这里有一个小技巧，考虑到小数不是太好处理，所以把所有元素都\(*2\)，此时\(\frac{s_1+s_2}{2}\)必为整数

看到两个数组和的表达方式，可以用\(n^2\)来枚举\(a_{i1},a_{j1}\)，同时用一个\(log\)在\(b_{i2}+b_{j2}\)中来查找

代码

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdio>
using namespace std;
struct node
{
    long long val;
    int x,y;
    friend bool operator < (const node &a,const node &b)
    {
        return a.val<b.val;
    }
    friend bool operator == (const node &a,const node &b)
    {
    	return a.val==b.val;
	}
};
int n,m;
long long ans=(1ll<<60);
long long s1,s2,s;
long long a[2005],b[2005];
vector<node> v;
vector<pair<int,int> > mem;
long long f_abs(long long val)
{
    return val<0?-val:val;
}
int main()
{
	ios::sync_with_stdio(false); 
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        a[i]*=2;
        s1+=a[i];
    }
    cin>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>b[i];
        b[i]*=2;
        s2+=b[i];
    }
    //不交换
    ans=min(ans,f_abs(s2-s1));
    //交换一次
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            if(ans>f_abs((s2-b[j]+a[i])-(s1-a[i]+b[j])))
            {
                mem.clear();
                ans=f_abs((s2-b[j]+a[i])-(s1-a[i]+b[j]));
                mem.push_back(make_pair(i,j));
            }
        }
    //交换二次
    s=s1+s2;
    for(int i=1;i<=m;i++)
        for(int j=i+1;j<=m;j++)
            v.push_back((node){b[i]+b[j],i,j});
    sort(v.begin(),v.end());
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            long long t=s1-a[i]-a[j];
            t=s/2-t;
            long long _ind=lower_bound(v.begin(),v.end(),(node){t,0,0})-v.begin();
			if(_ind!=v.size())
            {
                if(ans>f_abs((s2-v[_ind].val+a[i]+a[j])-(s1-a[i]-a[j]+v[_ind].val)))
                {
                    mem.clear();
                    mem.push_back(make_pair(i,v[_ind].x));
                    mem.push_back(make_pair(j,v[_ind].y));
                }
                ans=min(ans,f_abs((s2-v[_ind].val+a[i]+a[j])-(s1-a[i]-a[j]+v[_ind].val)));
            }
            _ind--;
            while(_ind>=0&&v[_ind].val>=t)
                _ind--;
            if(0<=_ind)
            {
                if(ans>f_abs((s2-v[_ind].val+a[i]+a[j])-(s1-a[i]-a[j]+v[_ind].val)))
                {
                    mem.clear();
                    mem.push_back(make_pair(i,v[_ind].x));
                    mem.push_back(make_pair(j,v[_ind].y));
                }
                ans=min(ans,f_abs((s2-v[_ind].val+a[i]+a[j])-(s1-a[i]-a[j]+v[_ind].val)));
            }
        }
    }
    cout<<ans/2<<endl;
    cout<<mem.size()<<endl;
    for(int i=0;i<mem.size();i++)
        cout<<mem[i].first<<‘ ‘<<mem[i].second<<endl;
    return 0;
}

习题：Professor GukiZ and Two Arrays (二分)

原文：https://www.cnblogs.com/loney-s/p/13387788.html