[UVa] 10487 Closest Sums.cpp

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