二分搜索 51Nod 1267 4个数和为0

我会带着你远行 2022-05-27 11:39 107阅读 0赞

题目链接：[https://www.51nod.com/onlineJudge/questionCode.html\#!problemId=1267][https_www.51nod.com_onlineJudge_questionCode.html_problemId_1267]

[1267 4个数和为0][https_www.51nod.com_onlineJudge_questionCode.html_problemId_1267] ![ok.png][]

基准时间限制：1 秒 空间限制：131072 KB 分值: 20 [难度：3级算法题][3]

![star.png][] 收藏

![plus.png][] 关注

给出N个整数，你来判断一下是否能够选出4个数，他们的和为0，可以则输出"Yes"，否则输出"No"。

Input

第1行，1个数N，N为数组的长度(4 <= N <= 1000)
    第2 - N + 1行：A[i]（-10^9 <= A[i] <= 10^9)

Output

如果可以选出4个数，使得他们的和为0，则输出"Yes"，否则输出"No"。

Input示例

5
    -1
    1
    -5
    2
    4

Output示例

Yes

排序后查找，不断改变 最大值和最小值

#include<cstdio> 
    #include<cstring>
    #include<algorithm>
    using namespace std;
    #define ll long long 
    const int MAXN=1009;
    ll a[MAXN];		//注意数据范围 
    int main()
    {
    	int n;
    	while(~scanf("%d",&n))
    	{
    		for(int i=0;i<n;i++)	scanf("%lld",&a[i]);
    		sort(a,a+n);
    		for(int i=0;i<n;i++)
    		{
    			for(int j=i+1;j<n;j++)
    			{
    				ll num=-(a[i]+a[j]);
    				int l=j+1,r=n-1;
    				while(l<=r)//算是二分么？，应该是吧 
    				{
    					if(a[l]+a[r]==num)
    					{
    						printf("Yes\n");
    						return 0;
    					}
    					if(a[l]+a[r]>num)
    						r--;
    					if(a[l]+a[r]<num)
    						l++;
    				}
    			}
    		}
    		printf("No\n");
    	}
    	return 0;
    }

[https_www.51nod.com_onlineJudge_questionCode.html_problemId_1267]: https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1267
[ok.png]: https://file.51nod.com/images/icon/ok.png
[3]: https://www.51nod.com/onlineJudge/problemList.html#!groupId=4
[star.png]: https://file.51nod.com/images/icon/star.png
[plus.png]: https://file.51nod.com/images/icon/plus.png