【CodeForces 620D】Professor GukiZ and Two Arrays

题

题意

两个数列，一个有n个数，另一个有m个数，让你最多交换两次两个数列的数，使得两个数列和的差的绝对值最小，求这个差的绝对值、最少交换次数、交换数对

分析

交换0次、1次可得到的最小的差可以枚举出来。

交换两次，如果枚举就超时了。

我们预处理把第一个数列两两组合的所有情况存储起来为u数组，并且按照大小排序，接着在另一个数列里枚举两个数后，用二分的方法，求交换后使得 差的绝对值最小 的u。

二分查找最接近的值可以用lower_bound函数。

代码

#include<stdio.h>
#include<cmath>
#include<map>
#include<utility>
#define N 2005
#define ll long long

using namespace std;
ll a[N],b[N],n,m,suma,sumb,v,ans,c;

map<ll,pair<int,int> >u;
map<ll,pair<int,int> >::iterator it;
pair<int,int>swap1,swap2;

void update(int i,int j)
{
    if(abs(c-it->first) < v)
    {
        ans=2;
        v = abs(c - it->first);
        swap1 = it->second;
        swap2 = {i,j};
    }
}

int main()
{
    scanf("%lld",&n);
    for(int i=1; i<=n; i++)
    {
        scanf("%lld",&a[i]);
        suma+=a[i];
    }

    scanf("%lld",&m);
    for(int i=1; i<=m; i++)
    {
        scanf("%lld",&b[i]);
        sumb+=b[i];
    }

    v=abs(suma-sumb);
    if(!v)
    {
        printf("0
0
");
        return 0;
    }

    for(int i=1; i<n; i++)
        for(int j=i+1; j<=n; j++)
            u[(a[i]+a[j])*2LL] = {i,j};

    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            if(abs(suma-sumb-2LL*(a[i]-b[j]))<v)
            {
                ans=1;
                v=abs(suma-sumb-2LL*(a[i]-b[j]));
                swap1= {i,j};
            }
    for(int i=1; i<m; i++)
        for(int j=i+1; j<=m; j++)
        {
            c=suma-sumb+2LL*(b[i]+b[j]);
            it=u.lower_bound(c);
            if( it != u.end() )
                update(i,j);
            if( it != u.begin() )
            {
                it--;
                update(i,j);
            }
        }

    printf("%lld
%lld
",v,ans);

    if(ans==1)printf("%d %d
",swap1.first,swap1.second);
    if(ans==2)printf("%d %d
%d %d
",swap1.first,swap2.first,swap1.second,swap2.second);

    return 0;
}

2017.7.21 ps. 今天再做这题，wa了八下。因为自己写的二分，一开始忘记考虑n==1的情况（这样就不存在a数组里选两个加起来了，二分的结果没有意义）。之后发现我二分查找的是加了绝对值的，显然不需要加绝对值。以及如果二分查找的值不存在，那么得到的就是大于它的第一个值，所以还要考虑小于它的第一个值。最终AC的代码如下：

#include <cstdio>
#include <algorithm>
#define ll long long
using namespace std;
#define N 2001
int n,m,a[N],b[N];
struct Node{
    ll a,b,v;
}sum[N*N];
ll sa,sb;
int x[2],y[2];
int cnt;
ll ans;
bool cmp(const Node& a,const Node& b){
    return a.v<b.v;
}
int bs(ll s){
    int l=1,r=cnt;
    while(l<r){
        int mid=l+r>>1;
        if(sum[mid].v<s)
            l=mid+1;
        else
            r=mid;    
    }
    return l;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d",a+i),sa+=a[i];
    scanf("%d",&m);
    for(int i=1;i<=m;++i)
        scanf("%d",b+i),sb+=b[i];

    for(int i=1;i<n;++i)
        for(int j=i+1;j<=n;++j)
            sum[++cnt]=(Node){i,j,2LL*(a[i]+a[j])};
    
    ans=abs(sb-sa);

    sort(sum+1,sum+1+cnt,cmp);
    int k=0;

    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j){
            ll t=abs(sa-a[i]*2-sb+b[j]*2);
            if(t<ans){
                ans=t;
                k=1;
                x[0]=i;y[0]=j;
            }
        }
    if(cnt){
        for(int i=1;i<m;++i)
            for(int j=i+1;j<=m;++j){
                ll t=sa-sb+2LL*(b[i]+b[j]);
                int d=bs(t);
                for(int g=-1;g<1;++g)if(d+g>0&&d+g<=cnt){
                    ll tans=abs(t-sum[d+g].v);
                    if(tans<ans){
                        ans=tans;
                        k=2;
                        x[0]=sum[d+g].a;y[0]=i;
                        x[1]=sum[d+g].b;y[1]=j;
                    }
                }    
            }
    }
    printf("%lld
%d
", ans,k);
    for(int i=0;i<k;++i)
        printf("%d %d
",x[i],y[i]);
    return 0;
}