PAT Advanced 1048. Find Coins (25) (C语言实现)
题目
Eva loves to collect coins from all over the universe, including some other
planets like Mars. One day she visited a universal shopping mall which could
accept all kinds of coins as payments. However, there was a special
requirement of the payment: for each bill, she could only use exactly two
coins to pay the exact amount. Since she has as many as
Input Specification:
Each input file contains one test case. For each case, the first line contains
2 positive numbers:
Output Specification:
For each test case, print in one line the two face values No Solution
instead.
Sample Input 1:
1
2
8 15
1 2 8 7 2 4 11 15
Sample Output 1:
1
4 11
Sample Input 2:
1
2
7 14
1 8 7 2 4 11 15
Sample Output 2:
1
No Solution
思路
可能是最简单的甲级题目之一了。
从诸多面值的硬币中找到正好凑齐交付金额的两枚硬币。鉴于面额的范围(1-500)很小,可以开一个数组记录不同面额硬币的数量,比较方便。
代码
Github最新代码,欢迎交流
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <stdio.h>
int main()
{
int N, M, counts[501] = {0}, coin;
scanf("%d %d", &N, &M);
for (int i = 0; i < N; i++) {
scanf("%d", &coin);
counts[coin]++;
}
for (int i = 1; 2 * i - 1 < M; i++) {
if ((i * 2 == M && counts[i] > 1)
|| (i * 2 != M && M - i < 501 && counts[i] && counts[M - i])) {
printf("%d %d", i, M - i);
return 0;
}
}
printf("No Solution");
return 0;
}