分析
因为只是单纯两个硬币凑目标数,所以可以用哈希表进行判断,一共两种情况:
- 当前钱数a[i]和m-a[i]在哈希表中都存在
- 当前钱数a[i]*2==m并且哈希表中a[i]个数大于等于2
为了输出最小序,可以直接把所有硬币排序。
附上pta原题链接:https://pintia.cn/problem-sets/994805342720868352/problems/994805432256675840
C++ 代码
#pragma GCC optimize(O2)
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int n,m;
int a[N];
unordered_map<int,int> mp;
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
mp[a[i]]++;
}
sort(a,a+n); //从小到大排序
int f=0;
for(int i=0;i<n;i++) //从最小开始枚举
if((mp.count(a[i]) && mp.count(m-a[i]) && a[i]!=m-a[i]) || (mp.count(a[i]) && a[i]*2==m && mp[a[i]]>1)) //满足条件
{
f=1;
printf("%d %d",a[i],m-a[i]);
break;
}
if(!f) puts("No Solution"); //最后没有找到答案,输出"No Solution".
return 0;
}