PAT(Advanced)1048 Find Coins C++实现

PAT(Advanced)1048 Find Coins C++实现

PAT(Advanced)甲级1048 Find Coins C++实现

题目链接

1048 Find Coins

题目大意

给定一组N个硬币面值序列和一个需要由两个硬币拼凑成的面值M，若能从序列中找到两个序列拼凑成对应面值，则输出两个面值，若存在多对这样的硬币，则输出最小的面值所在那一对，若找不到则输出No Solution

算法思路

根据题意，面值序列最大面值不超过500，则两个硬币最大面值不超过1000，开辟一个数组存放，数组下标为面值，数组内容为对应面值的硬币个数，第一个硬币面值从0开始到M，判断第二个硬币面值M-i是否存在即可，若硬币面值相等，则至少需要两个

AC代码

/*
author : eclipse
email  : eclipsecs@qq.com
time   : Mon Jun 22 08:46:08 2020
*/
#include <bits/stdc++.h>
using namespace std;const int MAX_SIZE = 1024;int main(int argc, char const *argv[]) {int N, M;scanf("%d%d", &N, &M);vector<int> faceValues;faceValues.resize(MAX_SIZE);for (int i = 0; i < N; i++) {int faceValue;scanf("%d", &faceValue);faceValues[faceValue]++;}for (int i = 0; i < M; i++) {if (faceValues[i] && faceValues[M - i]) {if (i == M - i) {if (faceValues[i] >= 2) {printf("%d %d", i, M - i);return 0;}} else {printf("%d %d", i, M - i);return 0;}}}printf("No Solution");return 0;
}

样例输入

8 15
1 2 8 7 2 4 11 15

样例输出

4 11

鸣谢

PAT

最后

• 由于博主水平有限，不免有疏漏之处，欢迎读者随时批评指正，以免造成不必要的误解！