「PAT乙级真题解析」Basic Level 1020 月饼 (问题分析+完整步骤+伪代码描述+提交通过代码)
给出月饼的库存量和总售价, 同时给出市场总需求量, 要求可能的最大收益. 问题转换: 优先通过售卖哪些种类的月饼来满足市场需求, 会得到最大收益?
#数据结构#算法#需求分析#c语言#pat考试
Table of Contents
乙级的题目训练主要用来熟悉编程语言的语法和形成良好的编码习惯和编码规范。从小白开始逐步掌握用编程解决问题。
问题分析
给出月饼的库存量和总售价, 同时给出市场总需求量, 要求可能的最大收益.
问题转换: 优先通过售卖哪些种类的月饼来满足市场需求, 会得到最大收益? 观察样例, 有 3 种月饼,其库存量分别为 18、15、10 万吨 总售价分别为 75、72、45 亿元. (每吨单价 75/18 = 4.167 72/15 = 4.8 45/10=4.5) 市场需求量20万吨. 样例给出的策略是先卖出全部 15 万吨第 2 种月饼、以及 5 万吨第 3 种月饼. 所以可以推断, 优先卖出单价高的月饼.(这也符合直觉和经验) 为了达到单价高的优先被选择售卖, 可以考虑单价从高到低排序然后依次售卖直到满足市场需求量.
由于排序是按照单价排, 计算时需要用到总量(总售价也可能用到), 所以这三个信息需要绑定在一起. 如果使用三个数组分别存储, 则排序过程中对数据的位置移动会变得极其复杂, 这里使用结构存储单种月饼的信息. 同时为了使用方便, 我们额外存储月饼的"单价信息", 这里不用每次使用的时候另外计算. 【"数据存储是为了使用"原则】
完整描述步骤
- 读取数据(月饼种类数, 市场最大需求量, 各种类月饼数据(这里考虑用结构体存储, 各个字段是浮点数))
- 从高到低排序
- 循环, 从单价高到低选择月饼, 用需求量减去库存, 如果需求量变成了0, 则完成售卖, 此时的收益是最大收益。
- 输出最大收益(按照指定格式)
伪代码描述
- get input category_amount, demand_amount and detail of each category (as structure datatype)
- sort cookies (or called mooncake?) by unit price descendingly
- for cookie_detail in cookies: if demand_amount == 0: break if demand_amount > cookie_detail.total_amount: total_profit = total_profit + cookie_detail.total_price demand_amount = demand_amount - cookie_detail.total_amount else: total_profit = cookie_detail.unit_price * demand_amount demand_amount = 0
- print total_profit (in required format)
完整提交代码
/*
# 分析
给出月饼的库存量和总售价, 同时给出市场总需求量, 要求可能的最大收益.
问题转换: 优先通过售卖哪些种类的月饼来满足市场需求, 会得到最大收益?
观察样例,
有 3 种月饼,其库存量分别为 18、15、10 万吨
总售价分别为 75、72、45 亿元.
(每吨单价 75/18 = 4.167 72/15 = 4.8 45/10=4.5)
市场需求量20万吨.
样例给出的策略是先卖出全部 15 万吨第 2 种月饼、以及 5 万吨第 3 种月饼.
所以可以推断, 优先卖出单价高的月饼.(这也符合直觉和经验)
为了达到单价高的优先被选择售卖, 可以考虑单价从高到低排序然后依次售卖直到满足市场需求量.
由于排序是按照单价排, 计算时需要用到总量(总售价也可能用到), 所以这三个信息需要绑定在一起.
如果使用三个数组分别存储, 则排序过程中对数据的位置移动会变得极其复杂, 这里使用结构存储单种月饼的信息.
同时为了使用方便, 我们额外存储月饼的"单价信息", 这里不用每次使用的时候另外计算. 【"数据存储是为了使用"原则】
# 完整描述步骤
1. 读取数据(月饼种类数, 市场最大需求量, 各种类月饼数据(这里考虑用结构体存储, 各个字段是浮点数))
2. 从高到低排序
3. 循环, 从单价高到低选择月饼, 用需求量减去库存, 如果需求量变成了0, 则完成售卖, 此时的收益是最大收益。
4. 输出最大收益(按照指定格式)
# 伪代码描述
1. get input category_amount, demand_amount and detail of each category (as structure datatype)
2. sort cookies (or called mooncake?) by unit price descendingly
3. for cookie_detail in cookies:
if demand_amount == 0: break
if demand_amount > cookie_detail.total_amount:
total_profit = total_profit + cookie_detail.total_price
demand_amount = demand_amount - cookie_detail.total_amount
else:
total_profit = cookie_detail.unit_price * demand_amount
demand_amount = 0
4. print total_profit (in required format)
*/
typedef struct {
double total_amount;
double total_price;
double unit_price;
} cookie;
int logic_to_sort_cookies(const void* a, const void* b){
/* 按照月饼单价降序排列.
return 0, a和b相等, 位置不变;
return 1, a>b, a在后;
return -1, a<b, a在前;
*/
cookie cookie_1 = *(cookie*)a;
cookie cookie_2 = *(cookie*)b;
return cookie_2.unit_price > cookie_1.unit_price;
}
int main(){
int category_amount, demand_amount;
scanf("%d %d\n", &category_amount, &demand_amount);
cookie all_cookies[category_amount];
for (int i = 0; i < category_amount; i++)
scanf("%lf", &all_cookies[i].total_amount);
for (int i = 0; i < category_amount; i++){
scanf("%lf", &all_cookies[i].total_price);
all_cookies[i].unit_price = all_cookies[i].total_price / all_cookies[i].total_amount;
}
qsort(all_cookies, category_amount, sizeof(cookie), logic_to_sort_cookies);
double total_profit = 0;
for (int i = 0; i < category_amount && demand_amount != 0; i++){
if (demand_amount >= all_cookies[i].total_amount){
demand_amount -= all_cookies[i].total_amount;
total_profit += all_cookies[i].total_price;
continue;
}
total_profit += demand_amount * all_cookies[i].unit_price;
demand_amount = 0;
}
printf("%.2f", total_profit);
return 0;
}