PAT 1048. 找硬币
原题链接
简单
作者:
YAX_AC
,
2024-11-18 15:47:54
,
所有人可见
,
阅读 2
//universe宇宙 shopping mallshopping mall大型购物中心,商场
#include <iostream>
#include <algorithm>
#include <unordered_set>
using namespace std;
int main()
{
int n, m;
int v1 = 1e5, v2 = -1;//v1 设置一个较大的值
cin >> n >> m;
unordered_set<int> S;
while (n--)
{
int x;
cin >> x;
int y = m - x;//x + y = m,对于输入的 x,在堆中查看有没有 y。
if (S.count(y))//如果有,则 x + y = m,是一组解
{
S.insert(x);//注意!!!是先查询再插入,否则会将一个数使用两次
//如果m = 14,x = 7先将x=7插入,在查询(14-7=7)的话,可以查到7,如果数组中只有一次7,回将一个7也当作一类解,即7 7,答案无解算成有解,错误
if (x > y)//判断该解的小面值是否小于 v1,如果是,则把该解存入 v1, v2.
swap(x, y);
if (x < v1)
{
v1 = x;
v2 = y;
}
}
else
S.insert(x);
}
if (v1 < 1e5)//如果存在解
cout << v1 << " " << v2;
else
cout << "No Solution";
}