PAT A1048 Find Coins

题目链接

解题思路

使用散列的思想，首先用一个int数组表示index，即输入的数据，然后将数据从小到大排序，从而实现有多对只输出a最小的那对，然后设置另外设置一个ans数组来计数每一个index，然后遍历index数组，用m减去当前值，然后ans计数减一，利用两数的差作为索引去ans判断是否存在，如果存在就打印，不存在就继续遍历。直到结束。

代码

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn=1e5+10;
int n,m,ind[maxn],ans[maxn]={false};

int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++){
        scanf("%d",&ind[i]);
    }
    memset(ans,0,sizeof(ans));
    sort(ind,ind+n);
    for(int i=0;i<n;i++){
        ans[ind[i]]++;
    }
    bool has=false;
    for(int i=0;i<n;i++){
        ans[ind[i]]--;//第一个数计数减一
        int x=m-ind[i];//x表示第二个数
        if (ans[x]>0){
            has=true;
            ans[x]--;
            printf("%d %d",ind[i],x);
            break;
        }
    }
    if (!has) printf("No Solution");
    return 0;
}