[UVa] 11057 Exact Sum.cpp

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