Openjudge-NOI题库-和为给定数

题目描述 Description

给出若干个整数，询问其中是否有一对数的和等于给定的数。  输入输出格式 Input/output 输入格式： 共三行： 第一行是整数n(0 < n <= 100,000)，表示有n个整数。 第二行是n个整数。整数的范围是在0到10^8之间。 第三行是一个整数m（0 <= m <= 2^30)，表示需要得到的和。 输出格式：
若存在和为m的数对，输出两个整数，小的在前，大的在后，中间用单个空格隔开。若有多个数对满足条件，选择数对中较小的数更小的。若找不到符合要求的数对，输出一行No。  输入输出样例 Sample input/output 样例测试点#1

输入样例：

4

2 5 1 4

6

输出样例：

1 5

 

思路：这题用二分查找最快，先把数组从小到大排序（我这用的是快排，目的是为了满足题目条件中的"若有多个数对满足条件，选择数对中较小的数更小的"）

 

代码如下：

1 #include <stdio.h> 2 #include <stdlib.h> 3 int fun(const void *a,const void *b) 4 { 5 return *(int*)a-*(int*)b; 6 } 7 int main() 8 { 9 int n,a[100002],m; 10 int i,l; 11 int r,mid; 12 scanf("%d",&n); 13 for(i=1;i<=n;i++) 14 { 15 scanf("%d",&a[i]); 16 } 17 qsort(a+1,n,sizeof(int),fun);//选出小的更小 18 scanf("%d",&m); 19 for(i=1;i<=n;i++) 20 { 21 l=i+1;//左 22 r=n;//右 23 while(l<=r) 24 { 25 mid=(l+r)/2; 26 if(a[mid]==m-a[i]) break;//找到了 27 else if(a[mid]>m-a[i]) r=mid-1;//中间大于，右往左移 28 else l=mid+1;//否则左边右移 29 } 30 if(a[mid]==m-a[i])//输出结果 31 { 32 printf("%d %d\n",a[i],m-a[i]); 33 return 0; 34 } 35 } 36 printf("No\n");//没有 37 return 0; 38 }

 

转载于:https://www.cnblogs.com/geek-007/p/5667447.html

总结

以上是生活随笔为你收集整理的Openjudge-NOI题库-和为给定数的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。