解法一:统计出现频率

币值的范围有限,可以统计每种面值硬币的出现次数(为了考虑同一面值*2等于所需金额的情况),然后按照 V 从小到大开始组合寻找答案。

  1. #include <bits/stdc++.h>
  2. const int MAX_N = 500;
  3. using namespace std;
  4. int main() {
  5. ios::sync_with_stdio(false);
  6. cin.tie(0);
  7. int N, M;
  8. cin >> N >> M;
  9. int coins[MAX_N + 1];
  10. fill(coins, coins + MAX_N + 1, 0);
  11. int tmp;
  12. for (int i = 0; i < N; ++i) {
  13. cin >> tmp;
  14. coins[tmp]++;
  15. }
  16. for (int i = 1; i < M; ++i) {
  17. if (coins[i] > 0) {
  18. coins[i]--;
  19. if (M - i <= MAX_N && coins[M - i] > 0) {
  20. cout << i << " " << M - i << "\n";
  21. return 0;
  22. }
  23. coins[i]++;
  24. }
  25. }
  26. cout << "No Solution\n";
  27. }