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;
}
推荐阅读
-
POJ - 27854 Values whose Sum is 0 (折半枚举,)
-
【POJ 2785】【折半枚举】4 Values whose Sum is 0【暑期 No.6】
-
4 Values whose Sum is 0 POJ - 2785
-
POJ 2785 4 Values whose Sum is 0
-
POJ 2785 4 Values whose Sum is 0(hash)
-
POJ-2785 4 Values whose Sum is 0(二分+双指针)
-
POJ2785 4 Values whose Sum is 0
-
4 Values whose Sum is 0 POJ - 2785
-
4 Values whose Sum is 0 (折半枚举)
-
POJ-3441:4 Values whose Sum is 0--多元素之和判定