UVa 11057 Exact Sum

想法：
　　先將書本價錢排序，然後i=0開始，.搜尋(用binary search)確認(M-book[i])是否存在，如果存在就先將該組答案暫時保存，因為題目有說如果有多組答案要寫出差距最小的那組，因為我們已經排序，所以越後面的答案的差距越小。

	#include <cstdio>
	#include <algorithm>
	using namespace std;
	int N,M,i; // N: number of books, M: money Peter has
	int book[10001]; // price of each book
	int Search (int n,int start){ //使用binary search
	int left=start;
	int right=N;
	int mid;
	while (left<=right){
	mid = (left+right)/2;
	if (n==book[mid]) return mid;
	if (n>book[mid]) left=mid+1;
	else right=mid-1;
	}
	return -1;
	}
	int main()
	{
	while (scanf("%d",&N)!=EOF){
	for (i=0;i<N;i++) scanf("%d",&book[i]);
	scanf("%d",&M);
	sort (book,book+N);
	int ans[10000],a=0;
	for (i=0;book[i]<(M/2);i++){
	if (Search(M-book[i],i+1)!=-1) {
	ans[a++]=book[i];
	}
	}
	printf("Peter should buy books whose prices are %d and %d.\n\n",ans[a-1],M-ans[a-1]);
	}
	return 0;
	}

view raw [UVa] 11057 Exact Sum.cpp hosted with ❤ by GitHub