POJ 2785: four values sum is zero

问题描述:

给定四个长度为n的数组A, B, C, D。 要求从每个数组中取一个数, 这样得到四个数, 并且这四个数的之和为0. 求这样组合的个数。

限制条件: 1<= n <= 4000

例如, 输入:

6-45 -41 -36 -36 26 -3222 -27 53 30 -38 -5442 56 -37 -75 -10 -6-16 30 77 -46 62 45格式是: 数组大小

数组A

数组B

数组C

数组D

输出:

5

分析:

四个数列的组合数a, b, c, d总共有 n * n * n * n = n^4, 这样复杂度太大。

如果将其对半的话, 即分为a + b + c + d = 0 ————》c + d = -(a + b), 也就是将其分为AB 和 CD, 再考虑, 问题就会被简化。 从两个数组C, D 分别选择出两个数进行组合总共有 n * n = n^2,, 这可以通过枚举出来。 然后将这n^2个数排好序, 然后用就可以采用二分搜索了。 这里可以调用lower_bound 和 upper_boud 函数解决了。

程序如下:

#include <iostream>#include <cstdio>#include <algorithm> // for std::upper_bound and std::lower_bound//std::sortusing namespace std;typedef long long Int64;const int MAX_N = 4000 + 10;int n;int A[MAX_N], B[MAX_N], C[MAX_N], D[MAX_N];int CD[MAX_N * MAX_N]; // store all the combinations of array C and Dint main() {freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);while(scanf("%d", &n) != EOF) {for(int i = 0; i < n; i++) {scanf("%d", &A[i]);}for(int i = 0; i < n; i++) {scanf("%d", &B[i]);}for(int i = 0; i < n; i++) {scanf("%d", &C[i]);}for(int i = 0; i < n; i++) {scanf("%d", &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);Int64 res = 0; // store the number of candidatesfor(int i = 0; i < n; i++) {for(int j = 0; j < n; j++) {int cd = -(A[i] + B[j]);// 取出C和D中和(存储在CD数组中)为cd的部分res += upper_bound(CD, CD + n * n, cd)- lower_bound(CD, CD + n * n, cd);}}// printf long long, Apparently %lld is the most common way,// but that doesn't// work on the compiler that I'm using (mingw32-gcc v4.6.0).// The way to do// it on this compiler is: %I64dprintf("%I64d \n", res); // printf long long int}return 0;}运行结果如下:

数最亮的星。如果有可能,我带你去远行。

POJ 2785: four values sum is zero

相关文章:

你感兴趣的文章:

标签云: