和为给定数

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

这道题是一道二分的题，只是我不用二分做得零分代码（超时）

#include<iostream> using namespace std; int arr[100001]; struct number{ int num1,num2; }num[1000001]; void BubbleSort(int n,int m){ for(int i=n;i<=m;i++){ for(int j=n;j<=m-i;j++){ if(num[j].num1>num[j+1].num1){ swap(num[j].num1,num[j+1].num1); swap(num[j].num2,num[j+1].num2); } } } } int main(){ int n; cin>>n; for(int i=1;i<=n;i++){ cin>>arr[i]; } long long m; cin>>m; int count=0; bool flag=false; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(arr[i]+arr[j]==m&&j!=i){ num[++count].num1=arr[i]; num[count].num2=arr[j]; flag=true; } } } if(!flag){ cout<<"No"; return 0; } BubbleSort(1,count); cout<<num[1].num1<<" "<<num[1].num2; }

经过二分优化的代码（还加入了scanf和printf加快速度）

#include<iostream> #include<algorithm> #include<cstdio> using namespace std; const int MAX_N=1e5+7; int a[MAX_N],n,m; bool bs(int x,int l,int r){ while(l<=r){ int mid=l+(r-l)/2; if(x<a[mid]){ r=mid-1; } else if(x==a[mid]){ return true; }else{ l=mid+1; } } return false; } int main(){ scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d",&a[i]); scanf("%d",&m); sort(a,a+n); int i; for(i=1;i<p=n;i++){ if(bs(m-a[i],i+1,n-1)){ printf("%d %d\n",a[i],m-a[i]); break; } } if(i==n-1){ printf("No"); } }