51Nod--1001--lower_bound(a,a+n,ans)-a

题目链接：https://www.51nod.com/Challenge/Problem.html#problemId=1001

给出一个整数K和一个无序数组A,A的元素为N个互不相同的整数,找出数组A中所有和等于K的数对。例如K = 8，数组A：{-1,6,5,3,4,2,9,0,8},所有和等于8的数对包括(-1,9)，(0,8)，(2,6)，(3,5)。

Input

第1行：用空格隔开的2个数，K N，N为A数组的长度。(2 <= N <= 50000，-10^9 <= K <= 10^9) 第2 - N + 1行：A数组的N个元素。（-10^9 <= Aii <= 10^9)

Output第1 - M行:每行2个数,要求较小的数在前面,并且这M个数对按照较小的数升序排列。不存在任何一组解则输出No Solution

Sample Input
8 9
-1 6 5 3 4 2 9 0 8
Sample Output
-1 9
0 8
2 6
3 5

以下代码只是简单的排序处理，暴力搜找满足目标要求的值，超时！
#include<algorithm> 
#include<cmath>
#include<cstring>
#include<queue>
#include<iostream>
using namespace std;
int main(){long sum,n,a[50010];cin>>sum>>n;for(int i=0;i<n;i++)cin>>a[i];sort(a,a+n);//对a进行排序  时间复杂度(O(nlngn))int cnt=0;for(int i=0;i<n;i++){long s=sum-a[i];for(int j=n-1;j>=0;j--)if(s==a[j]){cout<<a[i]<<" "<<s<<endl;cnt++;break;}if(cnt==n/2)break;//时间复杂度O(n^2) }if(cnt==0)cout<<"No Solution"<<endl; 
}

/*STL函数：lower_bound(a,a+n,ans)-a，对于已经排好序的数组，找a[i]>=ans的最小指针，提高的查找速度*/
#include<algorithm> 
#include<cmath>
#include<cstring>
#include<queue>
#include<iostream>
using namespace std;
int main(){long sum,n,a[50010];cin>>sum>>n;for(int i=0;i<n;i++)cin>>a[i];sort(a,a+n);//对a进行排序  时间复杂度(O(nlngn))int cnt=0;for(int i=0;i<n;i++){int ans=sum-a[i];int p=lower_bound(a,a+n,ans)-a;if(ans==a[p]){if(p<=i)break;else{cout<<a[i]<<" "<<ans<<endl;cnt=1;}}}if(cnt==0)cout<<"No Solution"<<endl; 
}