欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

AcWing寒假每日一题——Day11找硬币

程序员文章站 2022-07-12 22:02:53
...

找硬币

伊娃喜欢从整个宇宙中收集硬币。

有一天,她去了一家宇宙购物中心购物,结账时可以使用各种硬币付款。

但是,有一个特殊的付款要求:每张帐单,她只能使用恰好两个硬币来准确的支付消费金额。

给定她拥有的所有硬币的面额,请你帮她确定对于给定的金额,她是否可以找到两个硬币来支付。

输入格式
第一行包含两个整数 N N N M M M,分别表示硬币数量以及需要支付的金额。

第二行包含 N N N 个整数,表示每个硬币的面额。

输出格式
输出一行,包含两个整数 V 1 , V 2 , V1,V2, V1,V2,表示所选的两个硬币的面额,使得 V 1 ≤ V 2 V1≤V2 V1V2 并且 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, 1N105,
1 ≤ M ≤ 1000 1≤M≤1000 1M1000
输入样例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;
}
相关标签: 算法