PAT B 1020-アルゴリズムメモ順P 118

1020月餅(25分)
月餅は中国人が中秋節に食べる伝統的な食品で、地域によっていろいろな風味の月餅があります.すべての種類の月餅の在庫量、総価格、市場の最大需要量を与えて、得ることができる最大収益はいくらですか.
注意:販売時に在庫の一部を取り出すことができます.3種類の月餅があれば、その在庫量はそれぞれ18、15、10万トンで、総価格はそれぞれ75、72、45億元です.市場の最大需要量が20万トンしかない場合、私たちの最大収益戦略は15万トンの2種類目の月餅と5万トンの3種類目の月餅を全部売って、72+45/2=94.5(億元)を得るべきだ.
入力形式:
各入力にはテスト例が含まれています.各試験例は、1000を超えない正の整数Nが月餅の種類数を表し、500(万トン単位)を超えない正の整数Dが市場の最大需要量を表す.その後、一行はN個の正数を与えて月餅ごとの在庫量(万トン単位)を表す.最後の行はN個の正数を与えて各月餅の総価格(億元単位)を表す.数字の間はスペースで区切られています.
出力フォーマット:
各テスト例について、1行に最大収益を出力し、億元単位で小数点以下2桁まで正確にします.
サンプルを入力:

3 20
18 15 10
75 72 45

出力サンプル:

94.50

問題を解く上での注意事項
この问题は必ず构造体を使わなければならなくて、最初は构造体を使わないで1つのとても复雑な解法を书いて、とても愚かで、永远に最も良い解を追求します!!!
この問題は全体的に難しくなく、sortソート部分ではcmpで単価をソートしなければならない.この問題は貪欲で、単価で最適を求めなければならない.この場所で初めて84前後の数字を間違えて計算したので、注意すればいい.
 

#include
#include

using namespace std;
struct cargo
{
    double ton ;
    double price;
    double sprice;             // single price=sprice      ，    ~
} thing[1010];

bool cmp(cargo a,cargo b)       //        
{
    return a.sprice > b.sprice;
}
int main()
{
    int N;
    double D;
    scanf("%d%lf",&N,&D);

    for(int i = 0; i < N; i++)
    {
        scanf("%lf",&thing[i].ton);
    }

    for(int i = 0; i < N; i++)
    {
        scanf("%lf",&thing[i].price);
        thing[i].sprice = thing[i].price/thing[i].ton;  
//               ，      
    }

    sort(thing, thing + N, cmp);

    double sum = 0;
    for(int i = 0; i < N; i++)
    {
        if(thing[i].ton <= D)
        {
            D -= thing[i].ton;
            sum += thing[i].price;
        }
        else
          {
            sum += D*thing[i].sprice;
            break;
          }

    }

    printf("%.2lf",sum);//  ，        ，        ~

    return 0;
}