題目大意：給出n個數字，給出一個數字x，求出n個數字中哪兩個數字的和與x最接近。
我的做法是這樣的，把n個數字兩兩求和的結果存在數組里面，排序，去重（這一步無所謂）。每當給出一個x的時候，二分查找大于等于x的第一個數字，和小于x的最后一個數字。比較即可得出結果。
以下是我的代碼：
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
using namespace std;
int main()
{
#ifndef ONLINE_JUDGE
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
#endif
int case_num(0),n;
while(scanf("%d",&n)==1 && n)
{
vector<int> a,r;
for(int i=0;i<n;i++)
{
int t;
scanf("%d",&t);
a.push_back(t);
for(int j=0;j<i;j++)
r.push_back(a[j]+t);
}
sort(r.begin(),r.end());
r.erase(unique(r.begin(),r.end()),r.end());
/*
for(int i=0;i<r.size();i++)
{
if(i!=0)
printf(" ");
printf("%d",r[i]);
}
printf("\n");
//*/
case_num++;
printf("Case %d:\n",case_num);
int m;
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
int x;
scanf("%d",&x);
int dist(0x7f7f7f7f),ans;
vector<int>::iterator lpos(lower_bound(r.begin(),r.end(),x));
if(lpos!=r.end())
{
int t=*lpos;
if(dist>abs(t-x))
{
dist=abs(t-x);
ans=t;
}
}
if(lpos!=r.begin())
{
int t=*(lpos-1);
if(dist>abs(t-x))
{
dist=abs(t-x);
ans=t;
}
}
printf("Closest sum to %d is %d.\n",x,ans);
}
}
}
posted on 2011-05-19 19:34
lee1r 閱讀(426)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：排序