poj 2785 4 Values whose Sum is 0 折半枚举

缘起

日常浪费生命 poj 2785 4 Values whose Sum is 0

分析

此题也算是一道经典题目了（美团面试考过）

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
给定各有n个整数的四个数列 A，B，C，D，要从每个数列中各取出1个数字使得四个数的和为0.
求出这样的组合的个数. 当一个数列中有多个相同的数字时，把他们作为不同的数字看待.

【输入】
第一行输入n（1<=n<=4000）, 然后n行, 每行4个整数（该整数的绝对值<=1<<28）分别属于A,B,C,D四个数列

【输出】
输出组合数量

【样例输入】
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

【样例输出】
5

【限制】
15s

【hint】
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).

此题就是考察你知不知道 将a+b+c+d=0转换为 a+b=-c-d

所以O(N^2)枚举C和D中的数字两两求和，然后对这些和升序排序. 然后O(n^2)枚举a+b. 然后二分查找看看有几个即可. 整体算法复杂度是O(n^2logn)+O(n^2logn)=O(n^2logn)

而且因为折半枚举了，所以a+b不会超出int范围，不需要使用long long

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
//#include "stdafx.h"

#include <stdio.h>
#include <algorithm>
using namespace std;
//#define LOCAL

int n,a[4005],b[4005],c[4005],d[4005],e[16000005],num; // num是-c-d的值的个数, e用于存储-c-d的结果

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d", &n);
	for (int i = 0; i<(n<<2); i+=4)
	{
		scanf("%d%d%d%d", a+i/4,b+i/4, c+i/4,d+i/4);
	}
	for (int i = 0; i<n; i++) // 枚举c
	{
		for (int j = 0; j<n;j++) // 枚举d
		{
			e[num++] = -c[i]-d[j];
		}
	}
	sort(e,e+num); // 升序排序(注意, e中可能有重复元素)
	int ans = 0;
	for (int i = 0; i<n;i++) // 枚举a
	{
		for (int j = 0; j<n;j++) // 枚举b
		{
			int t = a[i]+b[j];
			int *lo = lower_bound(e,e+num,t),*hi = upper_bound(e,e+num, t);
			if (*lo == t) // 如果有等于t的
			{
				ans+=hi - lo; //看看 e中有几个=a+b的
			}
		}
	}
	printf("%d\n", ans);
	return 0;
}

ac情况

Status Accepted
Time 5797ms
Memory 24660kB
Length 849
Lang C++
Submitted 2019-09-02 17:33:38
Shared
RemoteRunId 20825885