[1649] Find Sum
- 时间限制: 1000 ms 内存限制: 65535 K
- 问题描述
This problem is really boring.
You are given a number sequence S which contain n integers and m queries, each time i will give your two integers id1 and id2, you need to tell me whether i can get S[id1] + S[id2] from the n integers.
- 输入
- Input starts with an integer T(T <= 5) denoting the number of test cases.
For each test case, n(1 <= n <= 100000, 1 <= m <= 10000) are given, and the second line contains n integers, each of them is larger then 0 and no larger than 10^11.
Next m lines, each line contains two integers id1 and id2(1 <= id1, id2 <= n). - 输出
- For each case, first print the case number.
For each query, print “Yes” if i can get S[id1] + S[id2] from S, otherwise print “No”(without the quote). - 样例输入
1
5 3
3 4 2 1 3
1 2
3 4
4 5- 样例输出
Case 1:
No
Yes
Yes
会了二分查找之后这类题型做起来简直爽翻。科科~果然二分一般都是最先接触的算法吗。。。注意一点就是题目中给的数据或者说中间数据会超出int范围，第一次交RE了，改成__int64就AC了
代码：
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
bool bi_search(const __int64 list[],const __int64 &len,const __int64 &goal)
{
__int64 l=0,r=len-1;
while (l<=r)
{
__int64 mid=(l+r)>>1;
if(list[mid]==goal)
return true;
else if(list[mid]<goal)
{
l=mid+1;
}
else
{
r=mid-1;
}
}
return false;
}
int main(void)
{
int t,q;
scanf("%d",&t);
for (q=1; q<=t; q++)
{
__int64 n,m,i,d1,d2;
scanf("%I64d%I64d",&n,&m);
__int64 *list=new __int64[n];//用来放初始值
__int64 *tlist=new __int64[n];//用来保存sort之后的有序序列，不然无法二分
for (i=0; i<n; i++)
{
scanf("%I64d",&list[i]);
tlist[i]=list[i];
}
sort(tlist,tlist+n);
printf("Case %d:\n",q);
for (i=0; i<m; i++)
{
scanf("%I64d %I64d",&d1,&d2);
if(bi_search(tlist,n,list[d1-1]+list[d2-1]))
printf("Yes\n");
else
printf("No\n");
}
delete []list;
delete []tlist;
}
return 0;
}