【PAT B 1020】月饼 贪心算法

硬核版本:思路是将储量,总价,单价保存在二维数组中。遍历每种月饼,每次找到单价最高的,如果剩余需求量大于储量,买完,然后将其设置为-1,标记为空;否则,将剩余需求量全部买为这种月饼。
出现的问题:变量max最开始没有设置为double,double转换为int时小数点后被舍弃,精度缺失。其次,没有考虑到需求量大于全部月饼储量总和的情况,究其根本在于while循环的break条件难以准确定义。与之相对,for循环能自动跳出,但需要对数组进行排序处理。

#include <iostream>
#include <cstdlib>
using namespace std;
const int maxn = 1005;
int main(void){
    int number,num;
    double list[maxn][3] = {0},price = 0,max,ton;
    bool isempty = false;
    cin >> number >> ton;
    for(int i = 0;i < number;i++)
        cin >> list[i][0]; //tons
    for(int i = 0;i <number;i++){
        cin >> list[i][1];
        list[i][2] = list[i][1] / list[i][0]; // price/per ton
    }

    while(ton){
        for(int i = 0;i < number;i++){
            if(max < list[i][2]){
                max = list[i][2];
                num = i;
            }
        }
        if(ton >= list[num][0]) {
            ton -= list[num][0];
            list[num][0] = 0;
            price += list[num][1];
            list[num][2] = 0;
            max = 0;
        }
        else if(ton < list[num][0]){
            price += list[num][2] * ton;
            ton = 0;
        }
        isempty = true;
        for(int i = 0;i < number;i++)
            if(list[i][0] > 0) {
                isempty = false;
            }
        if(isempty)
            break;
    }
    printf("%.2f",price);

    return 0;
}

排序处理的版本:主要是sort()函数的使用,其默认情况下为升序排列,第三个参数cmp的默认值为true,所以当为false时按降序排列。自定义cmp函数可以实现两重排序,例如在分数相同时将名字按照字典序排列。字典序简单来说,strcmp()比较后,字符串小的字典序小,要排在前面。

bool cmp(Student a, Student b){
    if(a.score != b.score) return a.score > b.score;
    else return strcmp(a.name ,b.name) < 0;
}

关键点:结构体数组,sort()函数,cmp()自定义比较函数,cin,cout和printf(),scanf()优缺点。

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

struct mooncake {
    double store;
    double sell;
    double price;
}cake[1005];

bool cmp(mooncake a, mooncake b){
    return a.price > b.price;
}

int main(void){
    int n;
    double need;
    cin >> n >> need;
    for(int i = 0;i < n;i++){
        cin >> cake[i].store;
    }
    for(int i = 0;i < n;i++){
        cin >> cake[i].sell;
        cake[i].price = cake[i].sell / cake[i].store;
    }
    sort(cake, cake + n, cmp);
    double ans = 0;
    for(int i = 0;i < n;i++){
        if(cake[i].store <= need){
            need -= cake[i].store;
            ans += cake[i].sell;
        }else{
            ans += cake[i].price * need;
            break;
        }
    }
    printf("%.2f",ans);

    return 0;
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容