AcWing 1532. 找硬币
原题链接
简单
作者:
每天被虐3000遍
,
2021-01-19 11:32:25
,
所有人可见
,
阅读 307
双指针
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<int> vec;
vec.resize(n, 0);
for (int i = 0; i < n; ++i) {
cin >> vec[i];
}
sort(vec.begin(), vec.end());
int low = 0, high = n - 1;
bool flag = false;
while (low < high) {
int sum = vec[low] + vec[high];
if (sum == m) {
flag = true;
cout << vec[low] << " " << vec[high] << endl;
break;
} else if (sum < m) {
++low;
} else {
--high;
}
}
if (!flag) {
cout << "No Solution" << endl;
}
return 0;
}
unordered_set
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<int> vec;
vec.resize(n, 0);
for (int i = 0; i < n; ++i) {
cin >> vec[i];
}
sort(vec.begin(), vec.end());
unordered_set<int> seen;
vector<pair<int, int>> ans;
for (auto &it : vec) {
int diff = m - it;
if (seen.find(diff) != seen.end()) {
if (diff > it) {
ans.emplace_back(make_pair(it, diff));
} else {
ans.emplace_back(make_pair(diff, it));
}
} else {
seen.insert(it);
}
}
if (ans.empty()) {
cout << "No Solution" << endl;
return 0;
}
sort(ans.begin(), ans.end(), [=](const pair<int, int> &a, const pair<int, int> &b) {
return a.first < b.first;
});
cout << ans.begin()->first << " " << ans.begin()->second << endl;
return 0;
}