作者：天使犯罪de快乐 | 来源：互联网 | 2023-05-29 17:25
1048.FindCoins(25)Evalovestocollectcoinsfromallovertheuniverse,includingsomeotherplanets
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(<=103, 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
V1 + V2 = M and V1 <=
V2. If such a solution is not unique, output the one with the
smallest V1. 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
题意
给定一系列硬币，以及一个商品的价格。要求从硬币中找到两个硬币让他们的组合等于商品的价格。如果有多个，输出有用最小单个值的硬币组合。
分析
思路1：hash
首先，硬币中币值不小于商品价格的可以过滤掉。遍历过程中，使用 hash 标记的方法，设定一个coins[MAXVALUE]（其中
MAXVALUE 为商品价格的最大值）记录已有的币值种类，
在遍历的过程中，一边将读入的硬币增加到coins[]中，一边计算满足条件的最小币值。
这个方法速度很快，数据读完，就差不多得到结果了。
思路2：先排序，然后两头扫
经典的2sum求和问题, 先给数组排序, 然后头尾指针分别从前后开始扫, 扫到的两个数的和若比给定的值要小, 那么头指针向后移动一步, 如果比给定的值大,
那么尾指针向前移动一步. 如果正好找到了, 那么就是他了, 返回.
hash
#include
using namespace std;
const int MAXVALUE = 1001;
int a[MAXVALUE];
int main()
{
int min = MAXVALUE;
int n, m;
int tmp;
scanf("%d%d", &n, &m);
for (int i = 0; i != n; ++i) {
scanf("%d",&tmp);
if (tmp < m) {
int tmpMin = tmp tmp;
if (a[m - tmp] == 1 && tmpMin < min) {
min = tmpMin;
}
a[tmp] = 1;
}
}
if (min != MAXVALUE) printf("%d %d\n", min, m - min);
else printf("No Solution");
return 0;
}
两头扫
#include
#include
#include
#define REP(i,n) for(int i=0;i<(n);++i)
using namespace std;
vector<int> vals;
int main(void) {
int N, M;
scanf("%d %d", &N, &M);
vals.resize(N);
REP(i, N) scanf("%d", &vals[i]);
int i=0;
int j=N-1;
sort(vals.begin(), vals.end());
bool found = false;
while(i < j) {
int sum = vals[i] + vals[j];
if(sum == M) {
found = true;
break;
}
else if(sum < M) {
i++;
}
else
j--;
}
if(found) {
printf("%d %d\n", vals[i], vals[j]);
}
else {
printf("No Solution\n");
}
return 0;
}
PAT 解题报告 1048. Find Coins (25),布布扣,bubuko.com
京公网安备 11010802041100号