1048. Find Coins.md

【PAT A-1048】Find Coins

题意概述

给出一个数列和一个正整数 M，判断数列中是否有 2 个数的和等于 M。

输入输出格式

输入第一行包含 2 个正整数：N（表示数列的长度）和 M。第二行给出 N 个整数，它们都是不超过 500 的正数。一行中的所有数字都用空格分隔。

在一行打印两个和等于 M 的两个数$V_1,V_2\left(V_1\le V_2\right)$。如果这样的解决方案不是唯一的，请输出 $V_1$ 最小的两个数。如果这样的两个数，输出No Solution。

数据规模

$$N\le{10}^5,M\le{10}^3$$

算法设计1

先将读取得到的数组 v 从小到大进行排序，然后遍历数组 v，遍历过程中，假设正在访问的元素索引为 i，数组长度为 N，那么可以在$\left[i+1,N\right)$的下标范围中通过二分查找算法查找是否存在数字$M-v[i]$。遍历一次数组时间复杂度为$O\left(n\right)$，进行一次二分查找时间复杂度为$O\left(logn\right)$，因此总的时间复杂度为$O\left(nlogn\right)$。

C++代码1

#include <bits/stdc++.h>
using namespace std;
using gg = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    gg ni, mi;
    cin >> ni >> mi;
    vector<gg> v(ni);
    for (gg& i : v) {
        cin >> i;
    }
    sort(v.begin(), v.end());
    for (gg i = 0; i < ni; ++i) {
        if (binary_search(v.begin() + i + 1, v.end(), mi - v[i])) {
            cout << v[i] << " " << mi - v[i] << "\n";
            return 0;
        }
    }
    cout << "No Solution\n";
    return 0;
}

算法设计2

先将读取得到的数组v从小到大进行排序。定义两个索引 i=0、j=N-1，如果i<j则进行循环并进行以下判断：

1. 如果v[i]+v[j]>M，令j左移一位；
2. 如果v[i]+v[j]<M，令i右移一位；
3. 如果A[i]+A[j]==M，说明找到了一组符合要求的两个数，输出，退出循环。

如果当i<j退出循环时仍然没有找到符合要求的两个数，则输出No Solution。

整个算法的时间复杂度为$O\left(n\right)$。

C++代码2

#include <bits/stdc++.h>
using namespace std;
using gg = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    gg ni, mi;
    cin >> ni >> mi;
    vector<gg> v(ni);
    for (gg& i : v) {
        cin >> i;
    }
    sort(v.begin(), v.end());
    for (gg i = 0, j = ni - 1; i < j;) {
        if (v[i] + v[j] == mi) {
            cout << v[i] << " " << v[j] << "\n";
            return 0;
        } else if (v[i] + v[j] > mi) {
            --j;
        } else {
            ++i;
        }
    }
    cout << "No Solution\n";
    return 0;
}