AcWing 1532. 找硬币
原题链接
简单
作者:
回头不是从前
,
2021-01-19 14:47:58
,
所有人可见
,
阅读 313
sol1 哈希表; sol2 排序+双指针
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
const int N = 1e5 + 10;
int d[N];
int n, m;
map<int, int> h;
// 哈希表
void sol1() {
for(int i = 0; i < n; ++i) h[m - d[i]] = i;
int mind = 1e9, maxd = -1;
map<int, int>::iterator iter;
for(int i = 0; i < n; ++i) {
iter = h.find(d[i]);
if(iter != h.end() && iter -> second != i) {
int t = d[iter -> second];
mind = min(mind, min(d[i], t)), maxd = max(maxd, max(d[i], t));
}
}
if(mind != 1e9) cout << mind << ' ' << maxd;
else cout << "No Solution";
}
// 排序+双指针
void sol2() {
sort(d, d + n);
int i = 0, j = n - 1;
while(i < j) {
int t = d[i] + d[j];
if(t == m) {cout << d[i] << ' ' << d[j]; break;}
else if(t > m) j--;
else i++;
}
if(i >= j) cout << "No Solution";
}
int main() {
cin >> n >> m;
for(int i = 0; i < n; ++i) cin >> d[i];
sol1();
// sol2();
return 0;
}