PAT乙级1020

Posted on | | Visitors:
Words count in article: 406 字 | Reading time ≈ 2 分

题目链接

https://pintia.cn/problem-sets/994805260223102976/problems/994805301562163200

题解

很容易看出这是个背包（非01背包）问题，直接用贪心求解即可。

需要注意的是，这里涉及到单价的计算，要注意整数计算会损失精度的问题，所以月饼的总价、库存量、单价都使用了double进行定义。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
// PAT BasicLevel 1020
// https://pintia.cn/problem-sets/994805260223102976/problems/994805301562163200

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Mooncake{
public:
    double totalPrice;  // 总价
    double storage;     // 库存量
    double unitPrice;   // 单价
    Mooncake(double storage){this->storage=storage;}
};

bool mooncakeCmp(Mooncake&,Mooncake&);

int main()
{
    // 月饼种类数 市场最大需求量
    int n;int demand;
    cin >> n >> demand;

    // n种月饼库存量和售价
    vector<Mooncake> mooncakeVec;
    double storage,totalPrice;
    for(int i=0;i<n;++i){
        cin >> storage;
        mooncakeVec.push_back(Mooncake(storage));
    }
    for (int i = 0; i < n; ++i){
        cin >> totalPrice;
        mooncakeVec[i].totalPrice = totalPrice;
        mooncakeVec[i].unitPrice = totalPrice/mooncakeVec[i].storage;
    }

    // 对商品进行排序
    sort(mooncakeVec.begin(),mooncakeVec.end(),mooncakeCmp);

    // 购买商品
    double profit=0.0;
    for(int i=0;i<n;i++){
        // 单种月饼全部购买
        if (demand >= mooncakeVec[i].storage){
            demand -= mooncakeVec[i].storage;
            profit += mooncakeVec[i].totalPrice;
        }
        // 单种月饼购买一部分库存
        else{
            profit += mooncakeVec[i].unitPrice * demand;
            break;//直接break了，就不把demand减成0了
        }
    }

    // 输出最大收益
    printf("%.2f",profit);

    //system("pause");
    return 0;
}

bool mooncakeCmp(Mooncake &m1, Mooncake &m2)
{
    // 单价降序排列
    return m1.unitPrice > m2.unitPrice;
}

作者：@臭咸鱼

转载请注明出处：https://www.cnblogs.com/chouxianyu/

欢迎讨论和交流!