pat1020⽉饼 (25) [贪⼼算法]

2021-05-09

⽉饼是中国⼈在中秋佳节时吃的⼀种传统⻝品，不同地区有许多不同⻛味的⽉饼。现给定所有种类⽉饼的库存量、总售价、以及市场的最⼤需求量，请你计算可以获得的最⼤收益是多少。注意：销售时允许取出⼀部分库存。样例给出的情形是这样的：假如我们有3种⽉饼，其库存量分别为 18、15、10万吨，总售价分别为75、72、45亿元。如果市场的最⼤需求量只有20万吨，那么我们最⼤收益策略应该是卖出全部15万吨第2种⽉饼、以及5万吨第3种⽉饼，获得 72 + 45/2 = 94.5（亿元）。

输⼊格式：

每个输⼊包含1个测试⽤例。每个测试⽤例先给出⼀个不超过1000的正整数N表示⽉饼的种类数、以及不超过500（以万吨为单位）的正整数D表示市场最⼤需求量。随后⼀⾏给出N个正数表示每种⽉饼的库存量（以万吨为单位）；最后⼀⾏给出N个正数表示每种⽉饼的总售价（以亿元为单位）。数字间以空格分隔。

输出格式：

对每组测试⽤例，在⼀⾏中输出最⼤收益，以亿元为单位并精确到⼩数点后2位。

输⼊样例：

1
2
3

3 20
18 15 10
75 72 45

输出样例：

94.50

分析：⾸先根据⽉饼的总价和数量计算出每⼀种⽉饼的单价，然后将⽉饼数组按照单价从⼤到⼩排序，根据需求量need的⼤⼩，从单价最⼤的⽉饼开始售卖，将销售掉这种⽉饼的价格累加到result中，最后输出result即可～

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct mooncake{	//相当于定义了一个静态类
     float mount, price, unit;
};
int cmp(mooncake a, mooncake b) {
     return a.unit > b.unit;
}
int main() {
     int n, need;
     cin >> n >> need;
     vector<mooncake> a(n);
	for (int i = 0; i < n; i++) scanf("%f", &a[i].mount);
     for (int i = 0; i < n; i++) scanf("%f", &a[i].price);
     for (int i = 0; i < n; i++) a[i].unit = a[i].price / a[i].mount;
     sort(a.begin(), a.end(), cmp);
     float result = 0.0;
     for (int i = 0; i < n; i++) {
         if (a[i].mount <= need) {
              result = result + a[i].price;
         } else {
             result = result + a[i].unit * need;
             break;
         }
         need = need - a[i].mount;
     }
     printf("%.2f",result);
     return 0;
}

本系列(PAT算法)作者mail：1302304703@qq.com(非本人)