Week4--B - 四个数列

ZJM 有四个数列 A,B,C,D，每个数列都有 n 个数字。ZJM 从每个数列中各取出一个数，他想知道有多少种方案使得 4 个数的和为 0。

当一个数列中有多个相同的数字的时候，把它们当做不同的数对待。

请你帮帮他吧！

Input
第一行：n（代表数列中数字的个数）（1≤n≤4000）

接下来的 n 行中，第 i 行有四个数字，分别表示数列 A,B,C,D 中的第 i 个数字（数字不超过 2 的 28 次方）

Output
输出不同组合的个数。

Sample Input
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

Hint
样例解释: (-45, -27, 42, 30), (26, 30, -10, -46), (-32, 22, 56, -46),(-32, 30, -75, 77), (-32, -54, 56, 30).

Time limit15000 ms
Case time limit5000 ms
Memory limit228000 kB
OS Linux
解题思路：如果用4个for循环直接查找，由于O(n4)不满足题目对时间的要求，因此需要对算法进行适当优化，可以采用二分法将时间复杂度降到O(n2).

find()函数是一个二分查找的函数实现，本题代码实现时先将a[],b[]两个数组的和求出，存入一个n*n的数组p[]中，并将其由小到大排序，定义sum[]数组存储p[]中每个数在p[]中出现的次数，再利用两个for循环将c[i],d[j]求和-s，利用二分查找（find()函数）找到与s相等的p[k]，ans+=sum[i],如果未找到则继续找c[i]+d[j+1]或c[i+1]+d[1]的相反数，直到查找完毕，输出ans。
实现代码如下：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>

using namespace std;

int n;
int a[4100], b[4100], c[4100], d[4100];
int sum[16100000],p[16100000],p2[16100000];
//二分查找
int find(int x, int num)
{
    int l = 1, r = num, ans = -1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (p[mid] == x)
        {
            ans = mid;
            //      l = mid + 1;
            r = mid - 1;
        }
        else if (p[mid] > x)
            r = mid - 1;
        else
            l = mid + 1;
    }
    return ans;
}
int main()
{

    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d %d %d %d", &a[i], &b[i], &c[i], &d[i]);//cin >> a[i] >> b[i] >> c[i] >> d[i];
    }
    int sum1 = 0, k = 1;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            p[k] = a[i] + b[j];
            k++;
        }
    }
    int cnt = 0;
    int f = n * n;
    sort(p + 1, p + f + 1);
    int temp = 0, num = 0x7fffffff;
    p[0] = 0x7fffffff;
//sum[i]用来存储p[]中值为p[i]数的个数
    for (int i = 1; i <= f; i++)
    {
        num = p[temp];
        if (p[i] != num)
        {
            sum[i]++;
            temp = i;
        }
        else
        {
            sum[temp]++;
            sum[i]++;
        }
    }
    int t = 0;
//让c[i]与d[i]相加，利用find()函数找出与-(c[i] + d[j])相等的数的下标
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            int s = -(c[i] + d[j]);
            t = find(s, temp);//temp是需要查找的最大位置
            if (t != -1)
                cnt += sum[t];
            else if (t == -1)
                continue;
        }
    }
    cout << cnt << endl;
    return 0;
}
/*
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
*/

总结：合理使用二分法可以有效将程序优化，降低求解所需时间。如果实验数据比较多，尽量用scanf（），不然容易超时，同时在定义数组的时候后一定要舍得，否则会TLE。

Week4--B - 四个数列

推荐阅读更多精彩内容