关于算法-数据结构: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;
}