PAT 1048 Find Coins (25分) 硬币面值做数组下标即排序

题目

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 105​​ coins with her, she definitely needs your help. You are supposed to tell her, for any given amount of money, whether or not she can find two coins to pay for it.

Input Specification: Each input file contains one test case. For each case, the first line contains 2 positive numbers: N (≤105​​ , the total number of coins) and M (≤10​3​​ , the amount of money Eva has to pay). The second line contains N face values of the coins, which are all positive numbers no more than 500. All the numbers in a line are separated by a space.

Output Specification: For each test case, print in one line the two face values V1 and V2 (separated by a space) such that V​1​​ +V2​​ = M and V​1​​ ≤V​2​​ . If such a solution is not unique, output the one with the smallest V​1​​ . If there is no solution, output No Solution instead.

Sample Input 1:

8 15
1 2 8 7 2 4 11 15

Sample Output 1:

4 11

Sample Input 2:

7 14
1 8 7 2 4 11 15

Sample Output 2:

No Solution

解析

题目：

给出n个正整数序列和一个目标值m。要求找出一对数字满足a+b=m，若这样的ab不唯一，则选择所有满足和为m的整数对中a值最小的那个。若不存在，输出"No Solution"

思路：

• 因为最终结果涉及到一个大小顺序的问题，所以我们直接让每一个数字作为数组元素的下标，统计其出现的次数，这样的化借助于下标就自动实现了排序，然后我们按顺序遍历数组元素，如果nums[a]和nums[m-a]同时存在，那就直接输出，结束程序。（后面即便有满足和为m的整数对，它的第一个元素的值只会更大）
• 注意对于每一个存在的nums[a]，再去判断nums[m-a]是否存在之前，需要nums[a]--，就相当于你已经把a从所有数字拿出来了，所以它的总次数要减1，然后再去剩下的元素中找和他配对的部分。判断过程结束后，nums[a]++，恢复它的出现次数，因为进行下一次判断时我们会选取另一个元素，所以在此之前要恢复原数组。

代码

#include <iostream>
using namespace std;

int coins[1001];

int main() {
    int n, m, x;
    cin >> n >> m;
    while (n-- > 0) {
        cin >> x;
        // 每个硬币出现的次数，正好实现按面值排序
        coins[x]++;
    }
    // 每个硬币最大面值是500
    // 按面值从小到大
    for (int i=  0; i <= 500; ++ i) {
        // 这个面值存在
        if (coins[i]) {
            // 选用这个硬币，数量-1
            coins[i]--;
            // 这个面值不能超过目标值，缺少部分m-i，若这个面值的硬币存在
            if (m > i && coins[m - i]) {
                // 按从小到大输出这两部分
                cout << i << " " << m - i << endl;
                return 0;
            }
            // 恢复这个硬币数量
            coins[i]++;
        }
    }
    cout << "No Solution";
    return 0;
}