欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

POJ - 27854 Values whose Sum is 0 (折半枚举,)

程序员文章站 2024-03-20 18:42:28
...

题目链接

题意: 有四个数组,分别从四个数组中找到四个数, 然后使这四个数的和为 零。

每个数组有4000个,我们四重for 循环肯定不现实,

这时候就可以先枚举一半,排序,

然后再枚举一半,在已排序过的数组中找需要的值。

这时候 用 upper_bound()- lower_bound() 可以快速实现找到值有多少个。

#include <algorithm>
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 4005;
int cd[N*N],a[N],b[N],c[N],d[N];
int n;
int main() {
    long long ans = 0;
    scanf("%d",&n);
    for (int i = 0; i < n; i++)
        scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cd[i * n + j] = c[i] + d[j];
    sort(cd,cd+n*n);
    int z;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++){
        z = -(a[i] + b[j]);
        ans += upper_bound(cd,cd+n*n,z) - lower_bound(cd,cd+n*n,z);
    }
    printf("%lld\n",ans);
    return 0;
}

 

相关标签: 折半枚举