傳送門(mén)

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

題目

月餅是中國(guó)人在中秋佳節(jié)時(shí)吃的一種傳統(tǒng)食品，不同地區(qū)有許多不同風(fēng)味的月餅?，F(xiàn)給定所有種類(lèi)月餅的庫(kù)存量、總售價(jià)、以及市場(chǎng)的最大需求量，請(qǐng)你計(jì)算可以獲得的最大收益是多少。
注意：銷(xiāo)售時(shí)允許取出一部分庫(kù)存。樣例給出的情形是這樣的：假如我們有3種月餅，其庫(kù)存量分別為18、15、10萬(wàn)噸，總售價(jià)分別為75、72、45億元。如果市場(chǎng)的最大需求量只有20萬(wàn)噸，那么我們最大收益策略應(yīng)該是賣(mài)出全部15萬(wàn)噸第2種月餅、以及5萬(wàn)噸第3種月餅，獲得 72 + 45/2 = 94.5（億元）。
輸入格式：
每個(gè)輸入包含1個(gè)測(cè)試用例。每個(gè)測(cè)試用例先給出一個(gè)不超過(guò)1000的正整數(shù)N表示月餅的種類(lèi)數(shù)、以及不超過(guò)500（以萬(wàn)噸為單位）的正整數(shù)D表示市場(chǎng)最大需求量。隨后一行給出N個(gè)正數(shù)表示每種月餅的庫(kù)存量（以萬(wàn)噸為單位）；最后一行給出N個(gè)正數(shù)表示每種月餅的總售價(jià)（以?xún)|元為單位）。數(shù)字間以空格分隔。
輸出格式：
對(duì)每組測(cè)試用例，在一行中輸出最大收益，以?xún)|元為單位并精確到小數(shù)點(diǎn)后2位。
輸入樣例：
3 20
18 15 10
75 72 45
輸出樣例：
94.50

分析

聲明double類(lèi)型的二維數(shù)組，模仿一個(gè)表存放月餅的庫(kù)存量、總售價(jià)和單價(jià)，然后利用qsort可以整行交換，來(lái)比大小，最后按照單價(jià)的高的，優(yōu)先作為收益。

注意：
double和int轉(zhuǎn)換要注意精度問(wèn)題。

遇到的坑：
1.題目中說(shuō)第一行兩個(gè)數(shù)是正整數(shù)，但是月餅的庫(kù)存量是正數(shù)，總售價(jià)也是正數(shù)，而不是正整數(shù)；
2.qsort對(duì)double類(lèi)型排序一定要注意！qsort對(duì)double類(lèi)型排序一定要注意！
qsort對(duì)double類(lèi)型排序一定要注意！
我考慮之后覺(jué)得最優(yōu)方法不要返回兩數(shù)相減的結(jié)果，而是返回兩數(shù)比大小的結(jié)果，將bool值作為int型返回。

原理是：
在對(duì)浮點(diǎn)或者double型比大小的時(shí)候一定要用三目運(yùn)算符，因?yàn)槿绻彩褂谜湍菢拥南霚p的話，如果是兩個(gè)很接近的數(shù)則可能返回一個(gè)小數(shù)（大于-1，小于1），而cmp的返回值是int型，因此會(huì)將這個(gè)小數(shù)返回0，系統(tǒng)認(rèn)為是相等，失去了本來(lái)存在的大小關(guān)系。

我覺(jué)得使用比大小得到的bool值作為返回還是比較簡(jiǎn)便的。

源代碼

//C/C++實(shí)現(xiàn)
#include <iostream>
#include <stdlib.h>

using namespace std;

int compare(const void *a_t, const void *b_t){
    double *a = (double *)a_t, *b = (double *)b_t;
    return b[2] > a[2];
}

int main(){
    int type, max;
    scanf("%d %d", &type, &max);
    double moonCake[type][3]; //行數(shù)一會(huì)換成type，n行三列，分別是庫(kù)存量、總售價(jià)、單價(jià)
    for(int i = 0; i < 2; ++i){
        for(int j = 0; j < type; ++j){
            scanf("%lf", &moonCake[j][i]);
        }
    }
    for(int l = 0; l < type; ++l){
        moonCake[l][2] = moonCake[l][1] / moonCake[l][0];
    }
    qsort(&moonCake[0], type, sizeof(moonCake[0]), compare);
    double profit = 0;
    double tmp = max;
    for(int k = 0; k < type && tmp != 0; ++k){
        if(moonCake[k][0] <= tmp){
            profit += moonCake[k][1];
            tmp -= moonCake[k][0];
        }
        else{
            profit += (moonCake[k][2] * tmp);
            tmp = 0;
        }
    }
    printf("%.2f\n", profit);
    return 0;
}