AcWing寒假每日一题——Day11找硬币
找硬币
伊娃喜欢从整个宇宙中收集硬币。
有一天,她去了一家宇宙购物中心购物,结账时可以使用各种硬币付款。
但是,有一个特殊的付款要求:每张帐单,她只能使用恰好两个硬币来准确的支付消费金额。
给定她拥有的所有硬币的面额,请你帮她确定对于给定的金额,她是否可以找到两个硬币来支付。
输入格式
第一行包含两个整数
N
N
N 和
M
M
M,分别表示硬币数量以及需要支付的金额。
第二行包含 N N N 个整数,表示每个硬币的面额。
输出格式
输出一行,包含两个整数
V
1
,
V
2
,
V1,V2,
V1,V2,表示所选的两个硬币的面额,使得
V
1
≤
V
2
V1≤V2
V1≤V2 并且
V
1
+
V
2
=
M
V1+V2=M
V1+V2=M
如果答案不唯一,则输出 V 1 V1 V1 最小的解。
如果无解,则输出 N o No No S o l u t i o n Solution Solution。
数据范围
1
≤
N
≤
105
,
1≤N≤105,
1≤N≤105,
1
≤
M
≤
1000
1≤M≤1000
1≤M≤1000
输入样例1:
8 8 8 15 15 15
1 1 1 2 2 2 8 8 8 7 7 7 2 2 2 4 4 4 11 11 11 15 15 15
输出样例1:
4 4 4 11 11 11
输入样例2:
7 7 7 14 14 14
1 1 1 8 8 8 7 7 7 2 2 2 4 4 4 11 11 11 15 15 15
输出样例2:
N o No No S o l u t i o n Solution Solution
分析: 先思考一下暴力怎么做,就是枚举每个硬币,找出加和与
M
M
M相等的两个硬币,更新最小值最后输出。
暴力代码:
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int a[N];
int main(){
int i,n,m,flag=0,j,res=10000;
cin>>n>>m;
for(i=0;i<n;i++){
cin>>a[i];
}
for(i=0;i<n;i++){
for(j=0;j<n;j++){
if(i!=j&&a[i]+a[j]==m){
flag=1;
res=min(min(a[i],a[j]),res);
}
}
}
if(flag) cout<<res<<" "<<m-res<<endl;
else cout<<"No Solution"<<endl;
但是会超时,所以可以用哈希表
代码:
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int a[N];
set<int> s;
int main(){
int n,i,m,x,res=100000,flag=0;
cin>>n>>m;
for(i=0;i<n;i++){
cin>>x;
s.insert(x);
if(s.count(m-x)>=1&&m!=2*x){
flag=1;
res=min(res,m-x);
}
}
if(flag) cout<<res<<" "<<m-res<<endl;
else cout<<"No Solution"<<endl;
}
第二种做法是双指针算法。
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int a[N];
int main(){
int n,i,j,m;
cin>>n>>m;
for(i=0;i<n;i++) cin>>a[i];
sort(a,a+n);
for(i=0,j=n-1;i<j;i++){
while(a[i]+a[j]>m) j--;
if(i<j&&a[i]+a[j]==m){cout<<a[i]<<" "<<a[j]<<endl; return 0;}
}
cout<<"No Solution"<<endl;
}
上一篇: [JS代码库]
推荐阅读
-
【acwing 寒假每日一题(入门组)】day23开心的金明
-
【acwing 寒假每日一题(入门组)】day38 画图
-
【acwing 寒假每日一题(入门组)】day25献给阿尔吉侬的花束
-
【acwing 寒假每日一题(入门组)】day14 棋盘挑战
-
【acwing 寒假每日一题(入门组)】day17 滑雪场设计
-
【acwing 寒假每日一题(入门组)】day18
-
【acwing 寒假每日一题(入门组)】day20 火星人
-
【acwing 寒假每日一题(入门组)】day19合唱队形
-
【acwing 寒假每日一题(入门组)】day16 阶乘
-
【acwing 寒假每日一题(入门组)】day21摘花生