题目描述
伊娃喜欢从整个宇宙中收集硬币。
有一天,她去了一家宇宙购物中心购物,结账时可以使用各种硬币付款。
但是,有一个特殊的付款要求:每张帐单,她只能使用恰好两个硬币来准确的支付消费金额。
给定她拥有的所有硬币的面额,请你帮她确定对于给定的金额,她是否可以找到两个硬币来支付
输入格式
第一行包含两个整数 N 和 M,分别表示硬币数量以及需要支付的金额。
第二行包含 N 个整数,表示每个硬币的面额。
输出格式
输出一行,包含两个整数 V1,V2,表示所选的两个硬币的面额,使得 V1≤V2 并且 V1+V2=M。
如果答案不唯一,则输出 V1 最小的解。
如果无解,则输出 No Solution。
数据范围
1≤N≤105,
1≤M≤1000
输入样例1:
8 15
1 2 8 7 2 4 11 15
输出样例1:
4 11
输入样例2:
7 14
1 8 7 2 4 11 15
输出样例2:
No Solution
算法1
双指针
考虑到答案可能有多个
我们需要最小的V1 答案,所以要进行硬币的排序。
同时本题目双指针也需要在有序的环境进行指针的移动
使用双指针 l r; 一头一尾 当两数相加大于目标值减少R ,当两数相减小于目标值增加L
C++ 代码
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
const int N = 100010;
int a[N];
int n,m;
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++) { cin >> a[i];}
sort(a,a+n);
int l = 0; int r = n - 1;
while (l < r) {
if (a[l] + a[r] > m) { r--; }
else if (a[l] + a[r] < m) { l++;}
else if (a[l] + a[r] == m) {break;}
}
if (l < r) {
cout << a[l] << " " << a[r] << endl;
}else{
cout << "No Solution" << endl;
}
return 0;
}
算法2
哈希
由于需要找到V1最小的答案 所以还是要排序
然后再记录了所有元素的哈希表中查找有无符合条件的另一个数字。
注意区分V1==V2的情况
C++ 代码
// 112314.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#include <iostream>
#include <map>
#include <algorithm>
#include <set>
using namespace std;
const int N = 100010;
int a[N];
int n,m;
map<int,int> mm;
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> a[i]; mm[a[i]]++;
}
sort(a, a + n); int solved = 0;
for (int i = 0; i < n; i++) {
//当前数字是a[i]; 那么我们就要寻找 m-a[i]是否存在
int find = m - a[i]; int need = 1;
if (a[i] == find) need = 2;
if (mm[find] >= need) {
solved = 1;
cout << a[i] << " " << find << endl;
break;
}
}
if (0 == solved) {
//还没有解决 打印"No Solution"
cout << "No Solution" << endl;
}
return 0;
}
写的好
很好理解 棒!!!
感谢你的评价