题解 SP1296 【SUMFOUR - 4 values whose sum is 0】

xixike · 2020-05-12 23:36:00 · 题解

这道题我们可以用4层循环做，复杂度10^4（肯定过不了）。

于是我们考虑优化，不难想到利用二分优化，我们可以进行两次二分。

第一次是思想上的，就是把A+B+C+D=0，转化为-（A+B）=C+D。（这样写是因为我的代码里是这样找的当然也可以写成A+B=-(C+D) ）

第二次是真正的二分，我们先用sum1存下来a_i+b_j的所有情况，用sum2存下来c_i+d_j的所有情况。枚举sum1中的每一个值，用二分查找在sum2中找所有满足和为0的数的个数，求和再输出就可以啦。

前置知识：

lower_bound(a+1,a+n+1,b); 意思是在下角标为1-n的数组a中找第一个大于等于b的地址，如果想要去值，需要减去a数组地址，即lower_bound(a+1,a+n+1,b)-a;

upper_bound(a+1,a+n+1,b);找的是第一个大于b的数的地址，剩下的与lower_bound()都一样。

注意：上面的两个函数都是二分（\log{n}）的复杂度

如果太懒不想写二分的话，可以用这两个函数代替（比如我qwq）

附代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 4010

using namespace std;

int a[N],b[N],c[N],d[N];
int sum1[N*N],sum2[N*N];         //预处理a+b和c+d，因为要二分，所以只能开一维数组
int len1,len2;

int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            sum1[++len1]=a[i]+b[j];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            sum2[++len2]=c[i]+d[j];
    sort(sum1+1,sum1+len1+1);
    sort(sum2+1,sum2+len2+1);
    int ans=0;
    for(int i=1;i<=len1;i++)
        ans+=upper_bound(sum2+1,sum2+len2+1,-sum1[i])-lower_bound(sum2+1,sum2+len2+1,-sum1[i]);   //因为可能有多个符合条件的组合，所以要这样写（自己理解一下）
    printf("%d\n",ans);
    return 0;
}