PAT A1070 Mooncake (25 分) 貪心

    題目大意：有N種月餅，給出每種月餅的庫存量和總價，現在需要重量D的月餅，輸出可能獲得的最大收入。

    顯然是依次選擇單價最高的月餅，直到總重量達到D為止。但這題的坑點在于D和庫存量和總價都需要設定成double型才能過。

AC代碼：

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>

using namespace std;

struct mooncake
{
    double storage;
    double price;
    double profit;
    bool operator < (const mooncake &other)
    {
        return this->profit > other.profit;
    }
};

int main()
{
    int N;
    double D;
    scanf("%d%lf", &N, &D);
    vector<mooncake> v(N);
    for (int i = 0; i < N; ++i)
        scanf("%lf", &v[i].storage);
    for (int i = 0; i < N; ++i)
    {
        scanf("%lf", &v[i].price);
        v[i].profit = v[i].price / v[i].storage;
    }
    sort(v.begin(), v.end());
    double sum = 0;
    for (int i = 0; i < N; ++i)
    {
        if(v[i].storage <= D)
        {
            sum += v[i].price;
            D -= v[i].storage;
        }
        else
        {
            sum += v[i].profit * D;
            D = 0;
            break;
        }
    }
    printf("%.2f", sum);
    return 0;
}