[PAT解題報告] 月餅 (25)
轉載from http://tech-wonderland.net/blog/pat-1070-mooncake.html
這個是貪心算法. 求得每種月餅的單位數(shù)量上的售價, 按照這個單位售價降序排列, 依次盡量取得單位售價比較高的去填充那個市場需求, 知道達到那個最大的市場需求. 所得到的利潤就是最大的. 換個角度就說市場的最大需求量固定, 那么我們當然希望這些個需求量里面單位數(shù)量的銷售價格越高越好, 所以我們降序排列就可以得到最大利潤. 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;
}
投遞曼倫商貿等公司6個崗位 >
