摘要：
1020. 月饼 (25) 示例显示，如果我们有三种月饼，库存分别为18万吨、15万吨和10万吨，总售价分别为75亿元、72亿元和45亿元。如果市场上的最大需求只有20万吨，我们的最大收入策略应该是销售所有15万吨第二类月饼和5万吨第三类月饼，并获得72+45/2=94.5亿元。对于每个测试案例，首先给出一个不超过1000的正整数N，表示月饼类型的数量，给出不超过500的正整数D，表示最大市场需求。
时间限制
100 ms
内存限制
65536 kB
代码长度限制
8000 B
判题程序
Standard
作者
CHEN, Yue
月饼是中国人在中秋佳节时吃的一种传统食品，不同地区有许多不同风味的月饼。现给定所有种类月饼的库存量、总售价、以及市场的最大需求量，请你计算可以获得的最大收益是多少。
注意：销售时允许取出一部分库存。样例给出的情形是这样的：假如我们有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位。
输入样例：3 20 18 15 10 75 72 45输出样例：
94.50
思路：利用map映射且递增特性，我们利用单价映射月饼总量和总价
注意：总量和总价是正数，并不一定是正数，还有月饼单价可能相同，所以我们使用multimap容器
1 // 1020.cpp : 定义控制台应用程序的入口点。 2 // 3 4 #include "stdafx.h" 5 #include<iostream> 6 #include<map> 7 #include<iomanip> 8 9 using namespace std; 10 11 struct food 12 { 13 double total;//总量 14 double total_price;//总价 15 }; 16 17 void get_money(multimap<double, food>& m, int D);//求得总价并打印 18 void input(multimap<double, food>& m, food p[], int N);//将信息输入并存进容器中 19 20 int main() 21 { 22 int N,D; 23 multimap<double, food> m; 24 25 cin >> N >> D; 26 27 food *p = new food[N]; 28 29 input(m, p, N);//将信息输入并存进容器中 30 31 get_money(m, D);//求得总价并打印 32 33 delete[] p; 34 35 return 0; 36 } 37 38 //将信息输入并存进容器中 39 void input(multimap<double,food>& m,food p[],int N) 40 { 41 for (int i = 0; i < N; ++i) 42 cin >> p[i].total; 43 44 for (int i = 0; i < N; ++i) 45 { 46 cin >> p[i].total_price; 47 48 //用单价映射月饼类 49 m.insert(pair<double, food>(p[i].total_price / p[i].total*1.0, p[i])); 50 } 51 } 52 53 //求得总价并打印 54 void get_money(multimap<double, food>& m, int D) 55 { 56 double sum = 0; 57 58 //反向迭代器 59 multimap<double, food>::reverse_iterator i=m.rbegin(), end = m.rend(); 60 61 while (D > 0&&i!=end) 62 { 63 //需求充足 64 if (i->second.total < D) 65 { 66 sum += i->second.total_price; 67 D -= i->second.total; 68 69 ++i; 70 } 71 else//所剩需求小于该类月饼总量 72 { 73 sum += D*(i->first); 74 75 D = 0; 76 } 77 } 78 79 cout << setiosflags(ios::fixed)<<setprecision(2) << sum << endl; 80 }