首页 > 代码库 > UVALive 6275 Joint Venture(查找等值)
UVALive 6275 Joint Venture(查找等值)
转载请注明出处:http://blog.csdn.net/u012860063?viewmode=contents
题意:
大意:问是否存在两块乐高的长度等于上面给出的长度;
一、二分查找版;
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; int n,num[1000047]; int main() { int i, j, x; while(scanf("%d",&x)!=EOF) { memset(num,0,sizeof(num)); scanf("%d",&n); for( i = 1; i <= n; i++) { scanf("%d",&num[i]); } sort(num+1,num+n+1); int ll = x*10000000, t,a,b; int l, r, mid; int flag = 0; for(i = 1; i <= n; i++) { l = i+1, r = n, mid = 0; t = ll-num[i]; while(l<=r) { mid = (l+r)/2; if(t > num[mid]) l = mid+1; else if(t < num[mid]) r = mid-1; else { flag = 1; a = num[i]; b = num[mid]; break; } } if(flag == 1) break; } if(flag == 0) printf("danger\n"); else printf("yes %d %d\n",a,b); } return 0; }
二、非二分查找版:
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; int n,num[1000047]; int main() { int i, j, x; while(scanf("%d",&x)!=EOF) { memset(num,0,sizeof(num)); scanf("%d",&n); for( i = 1; i <= n; i++) { scanf("%d",&num[i]); } sort(num+1,num+n+1); int ll = x*10000000, t,a,b; int l, r, mid; int flag = 0; j = n; i = 1; while(i<j) { if(num[i] + num[j] == ll) { flag = 1; a = num[i]; b = num[j]; break; } else if(num[i] + num[j] < ll) i++; else if(num[i] + num[j] > ll) j--; } if(flag == 0) printf("danger\n"); else printf("yes %d %d\n",a,b); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。