首页 > 代码库 > uva10487

uva10487

#include<iostream>
#include<algorithm>

using namespace std;

int n,m,k,cases,sum,arr[1005],S[1000000];


void calsum(){
	k=0;
	for (int i=0;i<n-1;i++){
		for (int j=i+1;j<n;j++){
			S[k++]=arr[i]+arr[j];
		}
	}
	sort(S,S+k);
}
int abs(int t){
	return t>0?t:-t;
}
void bisearch(){
	int low=0;
	int high=k-1;
	int mid;
	int flag=0;
	while(low<=high){
		mid=(low+high)/2;
		if (S[mid]<sum){
			low=mid+1;
			
		}
		else if (S[mid]>sum){
			high = mid-1;
		}
		else{
			flag = 1;
			break;
		}
	}
	if (flag)
		cout<<"Closest sum to "<<sum<<" is "<<sum<<"."<<endl;
	else{
		if (mid==0){
			cout<<"Closest sum to "<<sum<<" is "<<S[mid]<<"."<<endl;
		}
		else if (abs(S[mid-1]-sum)<abs(S[mid]-sum)){
			cout<<"Closest sum to "<<sum<<" is "<<S[mid-1]<<"."<<endl;
		}
		else cout<<"Closest sum to "<<sum<<" is "<<S[mid]<<"."<<endl;
	}
}
int main(){
	cases=0;
	while (cin>>n&&n){
		cases++;
		for (int i=0;i<n;i++){
			cin>>arr[i];
		}
		calsum();
		cin>>m;
		cout<<"Case "<<cases<<":"<<endl;
		while(m--){
			cin>>sum;
			bisearch();
		}
	}
	return 0;
}
很简单的一题,排序后二分查找找最接近的值,为什么会wa呢?一直搞不懂