PAT B1020

---

解决思路 :贪心法，每次选取单价最高的月饼。

先上一个自己错误的解法

#include <cstdio>

#include <algorithm>

using namespace std;

double num[1010];

double price[1005];

double ans = 0;

int main() {

    int n, d;

    scanf("%d%d", &n, &d);

    for (int i = 0; i < n; i++) {

        scanf("%lf", &num[i]);

    }

    for (int i = 0; i < n; i++) {

        scanf("%lf", &price[i]);

        price[i] = price[i] / num[i];

    }

    sort(price, price + n);

    for (int i = n - 1; i >= 0; i--) {

        while (num[i] > 0 && d > 0) {

            ans += price[i];

            num[i]--;

            d--;

        }

    }

    printf("%.2f", ans);

    return 0;

}

然后是题解

#include <cstdio>

#include <algorithm>

using namespace std;

struct mooncake {

    double store; //库存

    double sell;   //总价

    double price;  /单价

}cake[1010];

bool cmp(mooncake a, mooncake b) {

    return a.price > b.price;

}

int main() {

   int n;

   double D;

   scanf("%d%lf", &n, &D);

   for (int i = 0; i < n; i++) {

    scanf("%lf", &cake[i].store);

   }

   for (int i = 0; i < n; i++) {

    scanf("%lf", &cake[i].sell);

    cake[i].price = cake[i].sell / cake[i].store;

   }

   sort(cake, cake + n, cmp);

   double ans = 0;

   for (int i = 0; i < n; i++) {

    if (cake[i].store <= D) {    //如果需求高于月饼的库存

        D -= cake[i].store;    //先把第i种全部卖出

        ans += cake[i].sell;

    } else {                 //库存高于需求

        ans += cake[i].price * D;   //只售出该种月饼，数量为需求量，然后break；

        break;

    }

   }

   printf("%.2f", ans);

   return 0;

}