3441:4 Values whose Sum is 0(二分查找)

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;
}

  

上一篇:LeetCode 938. 二叉搜索树的范围和


下一篇:Android使用TabHost时报错Your content must have a TabHost whose id attribute is 'android.R.id.tabhost