PAT A1070 Mooncake(C++)

PAT甲级目录 | PAT乙级目录

题目描述

原题地址:A1070 Mooncake
中文版:B1020 月饼

解题思路

贪心算法,按照单价排序,优先售卖单价最高的月饼,卖完了再换下一种。

易错点:

  • 价格/库存都有可能不是整数

也许陌生的知识点

  • sort(S, S + n, cmp);
    • 排序函数,实现 [first, last) 范围内的排序,可以自定义排序策略 cmp 函数
    • 不带 cmp 参数的 sort 函数实现从小到大排序
    • 所需头文件: algorithm

代码示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;
const int maxn = 1010;
struct Mooncake{
double total_price, storage, ave_price;
}M[maxn];
bool cmp(Mooncake a, Mooncake b){ return a.ave_price > b.ave_price; }
int main(){
int N;
double bonus = 0.0, need, price[maxn], storage[maxn];
scanf("%d %lf", &N, &need);
for(int i = 0; i < N; i++) scanf("%lf", &M[i].storage);
for(int i = 0; i < N; i++) {
scanf("%lf", &M[i].total_price);
M[i].ave_price = 1.0 * M[i].total_price / M[i].storage;
}
sort(M, M + N, cmp);
int cnt = 0;
while(need > 0 && cnt < N){
int t = need > M[cnt].storage ? M[cnt].storage : need;
bonus += M[cnt++].ave_price * t;
need -= t;
}
printf("%.2f\n", bonus);
return 0;
}