问题标题: 酷町堂：5563 月饼(mooncake)

这题可以用贪心

按单价排序，贪心思路就是尽量选单价高的月饼

代码自己想想吧

for(int i=1;i<=n;i++)
    {
        if(a[i].num<t)
        {
            ans+=a[i].pri;
            t-=a[i].num;
        }
        else
        {
            ans+=a[i].avg*t;
            break;
        }
    }

贪心直接解决

贪心不行就模拟吧

同上上上

包思远在2021-09-18 20:23:57追加了内容

上上

核心：

typedef struct moon {
    double weight;
    double sum;
    double value;
}moon;
bool cmp(moon a, moon b){
    return a.value > b.value;
}


int n, need;
    double w=0, cost=0;


vector<moon> t(n);
    for (int i = 0; i < n; i++) 
        cin >> t[i].weight;

    for (int i = 0; i < n; i++) {
        cin >> t[i].sum;
            t[i].value = t[i].sum / t[i].weight;
    }
    sort(t.begin(), t.end(), cmp);
    int i = 0;
    while (w < need&&i<n) {
        if (w + t[i].weight < need) {
            w = w + t[i].weight;
            cost += t[i].sum;
            i++;
        }
        else {
            cost += t[i].value*(need - w);
            w = need;
            break;
        }
    }
    最后四舍五入输出cost

1

1