pat 甲级 1048 Find Coins
这道题的思路就是用一个哈希表存储硬币。我们使用set,会去重,但是题目存在v1==v2的情况,直接使用哈希表无法判断是否有两个相同的硬币。所以我们需要在存入硬币前进行判断。
对于每一枚硬币 x,先判断在集合中是否存在 y,使得 x + y = m。
如果存在,则是一组解,先插入集合,然后判断该解的小面值硬币是否小于 v1, 如果是,则存入 v1, v2。
如果不存在,则将x插入集合后跳过。
如果存在解,则输出。否则无解。
#include<iostream>
#include<cstring>
#include<set>
#include<algorithm>
using namespace std;
const int N=100010,M=1010;
int num[N],count1[M];
int main()
{
int n,m;
cin>>n>>m;
set<int> money;
int v1=1e9,v2;
for(int i=0;i<n;i++){
int x;
cin>>x;
int y=m-x;
if(money.count(y)){
money.insert(x);
if(x>y) swap(x,y);
if(x<v1) v1=x,v2=y;
}
else money.insert(x);
}
if(v1==1e9)
cout<<"No Solution"<<endl;
else
cout<<v1<<" "<<v2<<endl;
return 0;
}
原文地址:https://blog.csdn.net/weixin_50671259/article/details/136241676
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!