关于算法-数据结构:PAT甲级1070-Mooncake

题目粗心：

现有月饼需求量为D.已知n种月饼各自的库存量和总售价，问如何销售这些月饼，使得能够取得的收益最大。求最大收益。

算法思路：

此题是应用贪婪的思维来求解，个别为了取得最大收益，会首先将售价最高的月饼尽可能多的销售进来，因为在需求量肯定的状况下，单价高的月饼总售价也会更高，所以咱们对所有的月饼依照其单价从高到低进行排序，而后顺次遍历所有的月饼，如果以后月饼的数量小于等于需求量，那么就全副售出并计算收益和更新需求量，否则就卖出和需求量相等的月饼并计算收益和更新需要为0，在需求量为0的时候进行遍历即可。

留神点：

1、题目说数量为负数然而没说是正整数(positive integer)所以得将amount和D设置为double，不然测试点2会呈现谬误
2、在D==0的时候应该退出循环，并且不能在为0的时候就输入利润，否则测试点3谬误。

提交后果：

第一次测试：测试点2谬误。

谬误起因：amount定义为了int类型。
改过办法：将amount定义为double，并且为了不便计算将需求量也定义为double类型

*/

AC代码：

#include <cstdio>
#include <algorithm>

using namespace std;

struct MoonCake{
    double price;//总价
    double unit_price;//单价
    double amount;//数量
};

bool cmpByUnitPrice(MoonCake a,MoonCake b){
    return a.unit_price>b.unit_price;
}

int main(){
    int N;
    double D;
    scanf("%d %lf",&N,&D);
    MoonCake moonCakes[N];
    for (int i = 0; i < N; ++i) {
        scanf("%lf",&moonCakes[i].amount);
    }
    for (int i = 0; i < N; ++i) {
        scanf("%lf",&moonCakes[i].price);
        moonCakes[i].unit_price = moonCakes[i].price/moonCakes[i].amount;
    }
    // 依照单价从高到低排序
    sort(moonCakes,moonCakes+N,cmpByUnitPrice);
    double profit = 0;//总利润
    for (int j = 0; j < N; ++j) {
        if (moonCakes[j].amount<=D){
            // 以后月饼全副卖出
            profit += moonCakes[j].price;
            D -= moonCakes[j].amount;
        } else {
            // 卖出一部分
            profit += moonCakes[j].unit_price*D;
            D = 0;
        }
        if(D==0){
            // 需要为0退出循环
            break;
        }
    }
    printf("%.2lf",profit);
    return 0;
}