PAT A1070 Mooncake(C++)

发表于 | 分类于 | |
字数统计: 289 字 | 阅读时长 ≈ 1 分钟
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;
}