UC知道ACM求解2
来源：百度知道 编辑：UC知道 时间：2024/06/03 07:59:56
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 x B x C x D are such that a + b + c + d = 0 . In the following, we assume that all lists have the same size n .
Input
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 input file, your program has to write the number quadruplets whose sum is zero.
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
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
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 x B x C x D are such that a + b + c + d = 0 . In the following, we assume that all lists have the same size n .
Input
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 input file, your program has to write the number quadruplets whose sum is zero.
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
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
这道题如果直接背包的话最坏情况仍然是O(n^4)的,所以必须想办法把复杂度降下来.
分为左右两半分别枚举,则显然各枚举两列的话复杂度会降得最多.
考虑先把左半边的情况全存下来,然后查找右半边每个和的负数在左边的个数.
如果直接枚举查找,则复杂度仍然为O(n^4).
所以可以先把左边的结果排序,然后对右面的每对和做二分查找其负值.
这样的话,复杂度为O(n^2 log n),符合本题要求.
核心代码如下:
int cnt(int m)
{
int min=0,max=t,mid;
while (min<max)
{
mid=(min+max)/2;
if (sts[mid]>=m)
max=mid;
else
min=mid+1;
}
if (sts[min]!=m)
return 0;
int lb=min;
min=-1,max=t-1;
while (min<max)
{
mid=(min+max+1)/2;
if (sts[mid]<=m)
min=mid;
else
max=mid-1;
}
int hb=min;
return hb-lb+1;
}