解法一:统计出现频率
币值的范围有限,可以统计每种面值硬币的出现次数(为了考虑同一面值*2等于所需金额的情况),然后按照 V
从小到大开始组合寻找答案。
#include <bits/stdc++.h>
const int MAX_N = 500;
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int N, M;
cin >> N >> M;
int coins[MAX_N + 1];
fill(coins, coins + MAX_N + 1, 0);
int tmp;
for (int i = 0; i < N; ++i) {
cin >> tmp;
coins[tmp]++;
}
for (int i = 1; i < M; ++i) {
if (coins[i] > 0) {
coins[i]--;
if (M - i <= MAX_N && coins[M - i] > 0) {
cout << i << " " << M - i << "\n";
return 0;
}
coins[i]++;
}
}
cout << "No Solution\n";
}