|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
#include <cstdio> #include <cstring> #include <vector> #include <algorithm> #include <iostream> //#include <cstdlib> #define ll long long using namespace std; int a[1010]; vector<int> sum; int binarySearch(int num,int lw,int hi) { if(hi-lw==1) { int diff1 = abs(num-sum[lw]); int diff2 = abs(num-sum[hi]); if(diff1<diff2) return sum[lw]; else return sum[hi]; } int mid=(lw+hi)>>1; if(num<=sum[mid]) return binarySearch(num,lw,mid); else return binarySearch(num,mid,hi); return 0; } int main() { int n,qry,ans,num; int kase=1; while(scanf("%d",&n),n) { for(int i=0;i<n;i++) { scanf("%d",&a[i]); } sum.clear(); for(int i=0;i<n;i++) { for(int j=i+1;j<n;j++) sum.push_back(a[i]+a[j]); } sort(sum.begin(),sum.end()); int len=sum.size(); bool flag=false; scanf("%d",&qry); while(qry--) { scanf("%d",&num); ans = binarySearch(num,0,len-1); if(!flag) printf("Case %d:\n",kase++); flag=true; printf("Closest sum to %d is %d.\n",num,ans); } } return 0; } |