[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;
}

全部评论

相关推荐

6 收藏 评论
分享
牛客网
牛客企业服务