AcWing 1532. 找硬币
原题链接
简单
C++ 代码
先确定一个硬币,然后根据总和可以得出另一个硬币的大小,用二分法判断这个硬币是否存在
其中包括一种情况是用了两次同一个硬币,需要排除这种情况
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e5+5;
int a[N];
int n,m;
int find(int x){
int l=1;
int r=n;
while(l<=r){
int mid=(l+r)/2;
//cout << a[mid] << endl;
if(a[mid]==x){
return mid;
}
if(a[mid]>x){
r=mid-1;
}
if(x>a[mid]){
l=mid+1;
}
}
return 0;
}
int main()
{
cin >> n >> m;
for(int i=1;i<=n;i++){
cin >> a[i];
}
sort(a+1,a+n+1);
// for(int i=1;i<=n;i++){
// cout << a[i] <<" ";
// }
for(int i=1;i<=n;i++){
int x=a[i];
int y=m-a[i];
if(find(y)){
if(y==x && a[find(y)-1]!=x && a[find(y)+1]!=x){
break;
}
cout << x << " " << y << endl;
return 0;
}
}
cout << "No Solution" << endl;
return 0;
}