[数据结构与算法]题197.pat甲级练习-1048 Find Coins (25 分)

题197.pat甲级练习-1048 Find Coins (25 分)

一、题目

二、题解

本题要你从一堆硬币中找到两枚硬币能够凑成要的钱，可以直接转换成一直一枚硬币的值，去看要凑的钱-这枚硬币值得到的值的硬币是否存在，直接用哈希思想就好了。代码如下：

#include <bits/stdc++.h>

using namespace std;

int value[2001];//开大点应对M很大的情况，不然会段错误，因为下面要访问value[v2]，v2=M-i可能会超范围

int main()
{
    int N,M;
    cin>>N>>M;
    for(int i=0;i<N;i++)
    {
        int input;
        scanf("%d",&input);
        value[input]++;//直接哈希思想，用于标记这个下标对应coin的个数，刚好下标表示面值也省的排序了
    }
    int i;
    for(i=1;M-i>=i;i++)
    {
        if(value[i])
        {
            int v1=i;
            int v2=M-v1;
            value[i]--;
            if(value[v2])//直接用O(1)时间找到面值是否存在
            {
                printf("%d %d",v1,v2);
                break;
            }
        }
    }
    if(M-i<i)
    {
        printf("No Solution");
    }
}