1048 Find Coins

发表于

输入N和M，N是你手尚有的硬币数量，M为要求支付的金额。
接下来是N个数字，为硬币的面额。

注意相同金额的硬币可能有多个。输出要求V1+V2=M，V1<=V2，有多种结果取V1最小的。
面额不大于1000，所以从0到1000开始遍历，当前面额银币有，用掉，用掉的必须小于需要支付的金额。
再看，剩下金额的硬币手里是否有，有责直接输出，结束。
如果行不通，当然，拿出来的硬币要放回去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;
int a[1001];
int main() {
    int n, m, temp;
    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; i++) {
        scanf("%d", &temp);
        a[temp]++;
    }
    for(int i = 0; i < 1001; i++) {
        if(a[i]) {
            a[i]--;
            if(m > i && a[m-i]) {
                printf("%d %d", i, m - i);
                return 0;
            }
            a[i]++;
        }
    }
    printf("No Solution");
    return 0;
}