1020 月餅 (25分)
題目地址：https://pintia.cn/problem-sets/994805260223102976/problems/994805301562163200
月餅是中國人在中秋佳節時吃的一種傳統食品，不同地區有許多不同風味的月餅，現給定所有種類月餅的庫存量、總售價、以及市場的最大需求量，請你計算可以獲得的最大收益是多少，
注意：銷售時允許取出一部分庫存，樣例給出的情形是這樣的：假如我們有 3 種月餅，其庫存量分別為 18、15、10 萬噸，總售價分別為 75、72、45 億元，如果市場的最大需求量只有 20 萬噸，那么我們最大收益策略應該是賣出全部 15 萬噸第 2 種月餅、以及 5 萬噸第 3 種月餅，獲得 72 + 45/2 = 94.5（億元），
輸入格式：
每個輸入包含一個測驗用例，每個測驗用例先給出一個不超過 1000 的正整數 N 表示月餅的種類數、以及不超過 500（以萬噸為單位）的正整數 D 表示市場最大需求量，隨后一行給出 N 個正數表示每種月餅的庫存量（以萬噸為單位）；最后一行給出 N 個正數表示每種月餅的總售價（以億元為單位），數字間以空格分隔，
輸出格式：
對每組測驗用例，在一行中輸出最大收益，以億元為單位并精確到小數點后 2 位，
輸入樣例
3 20 18 15 10 75 72 45
輸出樣例
94.50
我的理解
輸入月餅種類數量，不同種類總售價，不同種類別庫存，計算各自單價，按照市場需求量和庫存數量的關系分情況進行計算，依次按照單價最高的優先，
- 獲取單價最高的月餅時，可以按照下面代碼中的依次找出最大值，也可以對月餅單價進行排序，但此時相應的庫存，和總售價也要進行相應的變化，可以將其封裝為一個結構體，
代碼段
#include <iostream>
using namespace std;
// 找到單價最高的月餅，回傳其下標位置
short findMaxUnitPrice(float unitPrice[], int n);
int main() {
// 月餅數量
short N = 0;
// 市場總需求量
short D = 0;
cin >> N >> D;
// 庫存
float stock[N];
// 總售價
float totalPrice[N];
// 單價
float unitPrice[N];
// 總收益
float maxProfit = 0.0;
for (int i = 0; i < N; i++) {
cin >> stock[i];
}
for (int i = 0; i < N; i++) {
cin >> totalPrice[i];
unitPrice[i] = totalPrice[i] / stock[i];
}
// 找到單價最高的月餅
short index = findMaxUnitPrice(unitPrice, N);
// 市場需求大于單個種類的月餅庫存
if (D > stock[index]) {
while (D > stock[index]) {
maxProfit += totalPrice[index];
D -= stock[index];
index = findMaxUnitPrice(unitPrice, N);
// 如果月餅全部已經“出售”
if (index == -1) {
break;
}
}
// 單種月餅的庫存量大于市場需求
if (index != -1) {
maxProfit += ((totalPrice[index] / stock[index]) * D);
}
} else {
// 單種月餅的庫存量大于市場需求
maxProfit += ((totalPrice[index] / stock[index]) * D);
}
printf("%0.2f\n", maxProfit);
return 0;
}
short findMaxUnitPrice(float unitPrice[], int n) {
float max = 0;
short index = -1;
for (int i = 0; i < n; i++) {
if (max < unitPrice[i]) {
max = unitPrice[i];
index = i;
}
}
// 如果月餅將要參與計算，則將其置為0
unitPrice[index] = 0;
return index;
}
更改程序
- 忽略市場需求大于月餅總庫存的情況，就是if （index == -1）的那個地方的判斷，導致陣列越界，可是C++好像你陣列越界之后，有時也是會回傳值的，不報例外，更可怕，
- 在使用findMaxUnitPrice函式找到單價最高的月餅之后，因為下次再找時，需要單價第二高的月餅，所以將其值置為0，下次仍然可以使用該函式，但是后面的總大收益maxProfit進行計算的時候，起初仍然直接用unitPrice[index] * D, 此時單價已經置為0了，導致最大收益偏低，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/102317.html
標籤：其他
上一篇：關于迷宮求解問題（八個方向）