首页 > 代码库 > XDOJ_1030_二分
XDOJ_1030_二分
http://acm.xidian.edu.cn/problem.php?id=1030
直接枚举前两个数,二分找第三个。
也可以先把正负分开,分两部分做,速度快了些,但要保存每个答案,耗内存。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int a[1005],n; int main() { while(~scanf("%d",&n)) { int flag = 1; for(int i = 1;i <= n;i++) scanf("%d",&a[i]); sort(a+1,a+1+n); for(int i = 1;i <= n-2;i++) { for(int j = i+1;j <= n-1;j++) { int sum = -a[i]-a[j]; int pos = lower_bound(a+j+1,a+n+1,sum)-a; if(pos <= n && a[pos] == sum) { flag = 0; printf("%d %d %d\n",a[i],a[j],a[pos]); } } } if(flag) printf("Ren Chou Jiu Gai Duo Du Shu!\n"); } return 0; }
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; struct anss { int a,b,c; }ans[1000000]; int a[1005],n; bool cmp(anss x,anss y) { if(x.a == y.a) return x.b < y.b; return x.a <y.a; } int main() { while(~scanf("%d",&n)) { for(int i = 1;i <= n;i++) scanf("%d",&a[i]); sort(a+1,a+1+n); int pos = lower_bound(a+1,a+1+n,0)-a; int cnt = 0; for(int i = 1;i < pos;i++) { for(int j = i+1;j < pos;j++) { int sum = -a[i]-a[j]; int x = lower_bound(a+pos,a+1+n,sum)-a; if(x <= n && a[x] == sum) { ans[cnt].a = a[i]; ans[cnt].b = a[j]; ans[cnt].c = a[x]; cnt++; } } } for(int i = pos;i <= n;i++) { for(int j = i+1;j <= n;j++) { int sum = -a[i]-a[j]; int x = lower_bound(a+1,a+pos,sum)-a; if(x < pos && a[x] == sum) { ans[cnt].a = a[x]; ans[cnt].b = a[i]; ans[cnt].c = a[j]; cnt++; } } } sort(ans,ans+cnt,cmp); if(cnt == 0) printf("Ren Chou Jiu Gai Duo Du Shu!\n"); for(int i = 0;i < cnt;i++) printf("%d %d %d\n",ans[i].a,ans[i].b,ans[i].c); } return 0; }
XDOJ_1030_二分
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。