首页 > 代码库 > 51nod 1267 4个数和为0
51nod 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-11-524
Output示例
Yes
二分
存下每两个数的和 然后二分
屠龙宝刀点击就送
#include <algorithm>#include <cstdlib> #include <cstdio>#define mo 20047#define mo2 13831using namespace std;struct node{ int x,y,z; bool operator<(node a)const { return z<a.z; }}h[1000001];int A[1001],cnt,n;int main(){ scanf("%d",&n); if(n<3) {printf("No");return 0;} for(int i=1;i<=n;i++) {scanf("%d",&A[i]);} for(int i=1;i<=n;i++) { for(int j=i+1;j<=n;j++) { h[++cnt].x=A[i]; h[cnt].y=A[j]; h[cnt].z=A[i]+A[j]; } } sort(h+1,h+1+cnt); int l=1,r=cnt; while(l<r-1) { int mid=(l+r)>>1; if(h[l].z+h[r].z==0&&h[l].x!=h[l].y&&h[r].x!=h[l].x&&h[r].y!=h[l].y&&h[l].x!=h[r].y&&h[l].y!=h[r].x) {printf("Yes");return 0;} if(h[l].z+h[r].z>0) r--; else if(h[l].z+h[mid].z<0) l++; else if(h[l].z+h[mid].z) break; } printf("No"); return 0;}
51nod 1267 4个数和为0
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。