题目描述
伊娃喜欢从整个宇宙中收集硬币。
有一天,她去了一家宇宙购物中心购物,结账时可以使用各种硬币付款。
但是,有一个特殊的付款要求:每张帐单,她只能使用恰好两个硬币来准确的支付消费金额。
给定她拥有的所有硬币的面额,请你帮她确定对于给定的金额,她是否可以找到两个硬币来支付。
样例
输入样例1:
8 15
1 2 8 7 2 4 11 15
输出样例1:
4 11
输入样例2:
7 14
1 8 7 2 4 11 15
算法1
(hash) $O(n)$
一次扫描
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <unordered_set>
using namespace std;
int n, m;
int main(){
unordered_set<int> hash;
cin >> n >> m;
int v1 = 1e9, v2;
for (int i = 0; i < n; i ++ ){
int a, b;
cin >> a;
b = m - a;
if (hash.count(b)){
hash.insert(a);
if (a > b) swap(a, b);
if (a < v1) v1 = a, v2 = b;
}else hash.insert(a);
}
if (v1 == 1e9) puts("No Solution");
else printf("%d %d\n", v1, v2);
return 0;
}
算法2
(双指针) $O(n^2)$
寻找$a_i + a_j \leq M$ 且$j 最大$, 那么必定满足$a_i + a_j = M$, 如果$j$再大那么就会使得$a_i + a_j > M$
当i往右边走的时候j必定往左边走。
证明:
存在$i’ > i, j’ > j$使得$a_{i’} + a_{j’} \leq M$, 那么因为$i < i’$,所以$a_i + a_{j’} <= M$, 因此对与$i$ 来说,因为取$j’$ 而不是$j$。
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1000010;
int n, m;
int w[N];
int main(){
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i ++ ) scanf("%d", &w[i]);
sort(w, w + n);
for (int i = 0, j = n - 1; i < j; i ++ ){
while (i < j && w[i] + w[j] > m) j --;
if (i < j && w[i] + w[j] == m){
printf("%d %d\n", w[i], w[j]);
return 0;
}
}
puts("No Solution");
return 0;
}