51nod-【1267 4个数和为0】

1267 4个数和为0 基准时间限制：1 秒 空间限制：131072 KB 分值: 20  难度：3级算法题  收藏  关注 给出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

想了2天，终于看懂了别人的代码，无语 上面有链接，题目说用二分，我不知道 这样的是不是二分，我本来用的二分结果有点麻烦，bug不少，现在介绍这个题题解 我们求4个数相加等于，，先排序（从小到大） 4个数相加等于0  前面2个数是比较小的数  后面2个数是不前面2个数大，但和他们的 相反数相等  sum1=a+b,sum2=c+d   sum1+sum2=0,a<b<c<d 我们可以挑出a b 然后在这个2个数的后面 找 c d  下面就需要举例说明核心算法 -3 -3 1 3 3 6 我们假设 a=-3, b=-3,  那么我们肯定是在  1 3 4 6 里面找 1的组合1+6=7,1+3=4,1+3=4 1 6 组合是1组合中最大的，小于7 那就换成 1 3 比4大那肯定是在 3 3组合中 本质就是每次增加最小值或者减小最小值 不说了，自己好好想想  

#include<cstdio> #include<algorithm> using namespace std; #define LL long long LL num[1100]; int main() { int n,i,j; scanf("%d",&n); for(i=0;i<n;++i) scanf("%lld",&num[i]); sort(num,num+n); for(i=0;i<n;++i) { for(j=i+1;j<n;++j) { LL sum=-num[i]-num[j]; int l=j+1,r=n-1; while(l<r) { if(num[l]+num[r]==sum) { printf("Yes\n"); return 0; } if(num[l]+num[r]>sum) --r; else ++l; } } } printf("No\n"); return 0; }