UVa 10487 Closest Sums

想法：
　　先將數列n排序好，之後n[j]從j=0開始，搜尋(q-n[j])，如果存在，則代表本題得解，如果不存在，則從最接近(q-n[j])的數字中挑選一個n[k]使得(n[i]+n[k])最接近q，將答案放入ans，然後j=1繼續搜尋...，直到n[j]>(q/2)為止，輸出ans。

	#include <cstdio>
	#include <algorithm>
	#include <cmath>
	using namespace std;
	int N,M;
	int n[1001],q[26];
	int Search(int a,int start){
	int L = start;
	int R = N-1;
	int mid;
	while (L<=R){
	mid = (L+R)/2;
	if (a==n[mid]) return mid;
	if (a>n[mid]) L = mid+1;
	else R = mid-1;
	}
	return mid;
	}
	int Closest(int q,int a,int b){
	if (abs(a-q) <= abs(b-q)) return a;
	else return b;
	}
	int main()
	{
	int Case=1,i,j;
	while (scanf("%d",&N)){
	if (N==0) break;
	for (i=0;i<N;i++) scanf("%d",&n[i]);
	sort (n,n+N);
	scanf("%d",&M);
	for (i=0;i<M;i++) scanf("%d",&q[i]);
	printf("Case %d:\n",Case++);
	for (i=0;i<M;i++){ // q loop
	int ans=n[0]+n[1];
	for (j=0;n[j]<=(q[i]/2) && j+1<N;j++){ // n loop
	int k = Search(q[i]-n[j],j+1);
	if ((n[j]+n[k])==q[i]) { ans = q[i]; break; }
	else {
	if (k-1!=j) ans = Closest(q[i],ans,n[j]+n[k-1]);
	ans = Closest(q[i],ans,n[j]+n[k]);
	if (k+1<N) ans = Closest(q[i],ans,n[j]+n[k+1]);
	}
	}
	printf("Closest sum to %d is %d.\n",q[i],ans);
	}
	}
	return 0;
	}

view raw [UVa] 10487 Closest Sums.cpp hosted with ❤ by GitHub