AcWing 1532. 找硬币
原题链接
简单
作者:
把这题一顿爆刷
,
2021-01-20 12:01:24
,
所有人可见
,
阅读 199
算法一
哈希表 $O(n)$
//算法一:哈希表 O(n)
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>
using namespace std;
int main(){
int n, m;
cin >> n >> m;
unordered_set<int> hash;
int v1 = 10000, v2;
for(int i = 0 ; i < n ; i++){
int a,b;
cin >> a;
b = m-a;
if(hash.count(b)){
hash.insert(a);
if(a>b) swap(a,b);
if(a<v1) v1 = a,v2 = b;
}
else hash.insert(a);
}
if(v1 == 10000) puts("No Solution");
else cout << v1 << ' ' << v2;
return 0;
}
算法二
双指针 $O(nlogn)$
C++ 代码
//算法二 双指针 O(nlogn)
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int n,m;
int a[N];
int main(){
cin >> n >> m;
for(int i = 0; i < n; i++) cin >> a[i];
sort(a,a+n);
for(int i = 0, j = n-1; i<j; i++){
while(i<j && a[i]+a[j] > m) j--;
if(i<j && a[i] + a[j] == m){
cout << a[i] << ' ' << a[j];
return 0;
}
}
cout << "No Solution";
return 0;
}
算法三:
二分法
C++ 代码
//算法三:二分法
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
int n,m;
int a[N];
int check(int j,int mid){
if(a[j] + a[mid] <= m) return true;
else return false;
}
int main(){
cin >> n >> m;
for(int i=0; i<n; i++) cin >> a[i];
sort(a,a+n);
for(int j=0; j<n-1; j++){
int r = n-1;
int l = j+1;
while(l<r){
int mid = (l+r+1)/2;
if(check(j,mid)) l=mid;
else r = mid-1;
}
if(a[j]+a[r] == m){
cout << a[j] << ' ' << a[r];
return 0;
}
}
cout << "No Solution";
return 0;
}