PAT甲题题解-1048. Find Coins (25)-水

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

给n，m以及n个硬币

问，是否存在两个硬币面值v1+v2=m

因为面值不会超过500，所以实际上最多500个不同的硬币而已

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <string.h>

using namespace std;

const int maxn=+;

int coin[maxn];

int n,m;

int main()

{

    scanf("%d %d",&n,&m);

    for(int i=;i<n;i++){

        scanf("%d",&coin[i]);

    }

    sort(coin,coin+n);

    int cnt=;

    int tmp[maxn];

    tmp[cnt++]=coin[];

    int num[maxn];  //统计该硬币出现的次数，因为可能m=a+a

    //因为硬币的大小不会超过500，所以实际上最多有500个不同的硬币

    for(int i=;i<n;i++){

        if(coin[i]!=coin[i-]){

            num[cnt]++;

            tmp[cnt++]=coin[i];

        }

        else{

            num[cnt-]++;

        }

    }

    bool flag=false;

    for(int i=;i<cnt;i++){

        int j=num[i]>=?i:i+;

        for(;j<cnt;j++){

            if(tmp[i]+tmp[j]==m){

                printf("%d %d\n",tmp[i],tmp[j]);

                flag=true;

                break;

            }

        }

        if(flag)

            break;

    }

    if(!flag)

        printf("No Solution\n");

    return ;

}