解法一:统计出现频率
币值的范围有限,可以统计每种面值硬币的出现次数(为了考虑同一面值*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";}
