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;
}