题目描述
这个题看起来很简单,看到第一眼就考虑枚举,但是暴力枚举是会超时的,就尝试了枚举加二分搜索,成功ac
算法1
(枚举+二分) $O(n^2)$
时间复杂度
n*log n;
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
int a[100002];
int main()
{
int v1,v2;
int n,m;cin>>n>>m;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
sort(a,a+n);
for(int i=0;i<n;i++)
{
v1=a[i];
v2=m-v1;
int left=0,right=n-1;
int mid=(left+right)/2;
while(left<=right)
{
mid=(left+right)/2;
if(a[mid]==v2&&mid!=i)//注意不要再次搜到自身 14=7+7,如果7是同一枚硬币不算
{
cout<<v1<<" "<<v2;
return 0;
}
else if(a[mid]<v2)left=mid+1;
else right=mid-1;
}
}
cout<<"No Solution";
return 0;
}