UVA 1152 4 Values whose Sum is 0

发表于   |   分类于   |     |   阅读次数

题目描述

Description

The SUM problem can be formulated as follows: given four lists A, B, C, D of integer values, compute how many quadruplet (a, b, c, d) ∈ A × B × C × D are such that a + b + c + d = 0. In the following, we assume that all lists have the same size n.

Input

The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.

The first line of the input file contains the size of the lists n (this value can be as large as 4000). We then have n lines containing four integer values (with absolute value as large as 228) that belong respectively to A, B, C and D.

Output

For each test case, your program has to write the number quadruplets whose sum is zero.

The outputs of two consecutive cases will be separated by a blank line.

Sample Input

1

6
-45 22 42 -16
-41 -27 56 30
-36 53 -37 77
-36 30 -75 -46
26 -38 -10 62
-32 -54 -6 45

Sample Output

5

Sample Explanation: Indeed, the sum of the five following quadruplets is zero: (-45, -27, 42, 30), (26, 30, -10, -46), (-32, 22, 56, -46), (-32, 30, -75, 77), (-32, -54, 56, 30).

题目链接

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3593

解题思路

题意：给n行4列数，要求每列选一个数，使4个数相加起来的和为0。

很容易就想到了O(n^4)算法，但是很显然题目不是让我们这样做，于是就想到了二分的方法。首先我们先把前两列和后两列的数分别两两组合，这样就得到了两个数组a和b，接着把b数组排一下序，然后使用二分查找遍历a，在b中寻找等于-a[i]的元素的数量，然后将数量累加就是最后的结论。

要注意两组输出数据之间有一个空行，但是最后一组数据没有空行。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <cstdio>
#include <algorithm>
using namespace std;

int res[5005][5];
int a[16000005], b[16000005];
int main()
{
    int t, n;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < 4; j++)
                scanf("%d", &res[i][j]);
        }
        int index = 0;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                a[index++] = res[i][0] + res[j][1];
            }
        }
        index = 0;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                b[index++] = res[i][2] + res[j][3];
            }
        }
        sort(b, b + index);
        int ans = 0;
        for (int i = 0; i < index; i++)
        {
            int pos = lower_bound(b, b + index, -a[i]) - b;
            while (b[pos] == -a[i] && pos < index)
            {
                ans++;
                pos++;
            }
        }
        printf("%d\n", ans);
        if (t) printf("\n");
    }
    return 0;
}