AcWing寒假每日一题——Day11找硬币

1532找硬币

一、问题描述

伊娃喜欢从整个宇宙中收集硬币。有一天，她去了一家宇宙购物中心购物，结账时可以使用各种硬币付款。但是，有一个特殊的付款要求：每张帐单，她只能使用恰好两个硬币来准确的支付消费金额。给定她拥有的所有硬币的面额，请你帮她确定对于给定的金额，她是否可以找到两个硬币来支付。
输入格式
第一行包含两个整数 N N N 和 M M M，分别表示硬币数量以及需要支付的金额。
第二行包含 N N N 个整数，表示每个硬币的面额。
输出格式
输出一行，包含两个整数 V 1 , V 2 V_1,V_2 V1​,V2​，表示所选的两个硬币的面额，使得 V 1 ≤ V 2 V_1≤V_2 V1​≤V2​ 并且 V 1 + V 2 = M V_1+V_2=M V1​+V2​=M。
如果答案不唯一，则输出 V 1 V_1 V1​ 最小的解。如果无解，则输出 No Solution。
数据范围
1≤ N N N≤ 1 0 5 10^5 105,
1≤ M M M≤ 1000 1000 1000
输入样例：

8 15
1 2 8 7 2 4 11 15

输出样例：

4 11

二、问题分析

本题可以用哈希表做，但是本人暂时不会，后续回补上，下面是双指针做法。
代码如下（示例）：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n, m;
int q[100010];
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
    sort(q, q + n);
    for (int i = 0, j = n - 1; i < j; i ++ )
    {
        while (i < j && q[i] + q[j] > m) j -- ;
        if (i < j && q[i] + q[j] == m)
        {
            printf("%d %d\n", q[i], q[j]);
            return 0;
        }
    }
    puts("No Solution");
    return 0;
}