[PAT解题报告] 月饼 (25)
转载from http://tech-wonderland.net/blog/pat-1070-mooncake.html
这个是贪心算法. 求得每种月饼的单位数量上的售价, 按照这个单位售价降序排列, 依次尽量取得单位售价比较高的去填充那个市场需求, 知道达到那个最大的市场需求. 所得到的利润就是最大的. 换个角度就说市场的最大需求量固定, 那么我们当然希望这些个需求量里面单位数量的销售价格越高越好, 所以我们降序排列就可以得到最大利润. AC代码如下:
#include <cstdio>
#include <algorithm>
#include <vector>
struct Node {
double amount;
double price;
};
bool cmp(const Node &n1, const Node &n2) {
return n1.price * n2.amount > n2.price * n1.amount;
}
double gao(int n, double d, std::vector<Node> &cakes) {
std::sort(cakes.begin(), cakes.end(), cmp);
double profit = 0.0;
for(int i = 0; d > 0 && i < n; ++i) {
int sell = std::min(d, cakes[i].amount);
profit += cakes[i].price * (sell * 1.0 / cakes[i].amount);
d -= sell;
}
return profit;
}
int main() {
int N, D;
scanf("%d %d", &N, &D);
std::vector<Node> cakes(N);
for(int i = 0; i < N; ++i)
scanf("%lf", &cakes[i].amount);
for(int i = 0; i < N; ++i)
scanf("%lf", &cakes[i].price);
printf( "%.2lf\n", gao(N, D, cakes) );
return 0;
}
