3441:4 Values whose Sum is 0
- 总时间限制:
- 15000ms
- 单个测试点时间限制:
- 5000ms
- 内存限制:
- 228000kB
- 描述
- 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 .
- 输入
- 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 .
- 输出
- For each input file, your program has to write the number quadruplets whose sum is zero.
- 样例输入
-
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
- 提示
- 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).
- 拿到题目刚开始用的四重遍历,发现超时,想到了先先把数组两两合并成两个数组,然后直接二分查找,提交提示错误,后来返现忘记考虑数组中重复元素的情况。题目不难,第一次遇到可能会漏想。
- 先贴忘记考虑重复元素的错误代码
-
#include <bits/stdc++.h> using namespace std; int main() { int n; while(cin>>n) { int ans=0; int a[n],b[n],c[n],d[n],sum1[n*n],sum2[n*n]; for(int i=0; i<n; i++) { cin>>a[i]>>b[i]>>c[i]>>d[i]; } int num=0; for(int i=0; i<n; i++) { for(int j=0; j<n; j++) { sum1[num]=a[i]+b[j]; sum2[num]=c[i]+d[j]; num++; } } sort(sum1,sum1+num); sort(sum2,sum2+num); for(int i=0; i<num; i++) { int left=0,right=num-1; while(left<=right) { int mid=left+(right-left)/2; if(sum1[i]+sum2[mid]==0) { ans++; break; } else if(sum1[i]+sum2[mid]>0)right=mid-1; else left=mid+1; } } cout<<ans<<endl; } return 0; }
下面贴上改正后的代码。
#include <bits/stdc++.h> using namespace std; int main() { int n; while(cin>>n) { int ans=0; int a[n],b[n],c[n],d[n],sum1[n*n],sum2[n*n]; for(int i=0; i<n; i++) { cin>>a[i]>>b[i]>>c[i]>>d[i]; } int num=0; for(int i=0; i<n; i++) { for(int j=0; j<n; j++) { sum1[num]=a[i]+b[j]; sum2[num]=c[i]+d[j]; num++; } } sort(sum1,sum1+num); sort(sum2,sum2+num); for(int i=0; i<num; i++) { int left=0,right=num-1; while(left<right) { int mid=left+(right-left)/2; if(sum1[i]+sum2[mid]>=0)right=mid; else left=mid+1; } while(sum1[i]+sum2[left]==0&&left<num){ ans++; left++; } } cout<<ans<<endl; } return 0; }