分面包｜优先队列贪心哈夫曼树

第六题 - A24635.分面包

题目链接跳转：A24635.分面包

这道题正着思考比较麻烦，但可以反着思考（选择从小面包逐步拼成大面包，而不是从大面包逐步切割成小面包）。不难发现反着思考后就是一个典型的贪心问题（哈夫曼树）。假设现在有 $N$ 块长度不一的小面包，那么将这些小面包合并成稍大一些的面包的最优策略就是选择剩下的小面包中长度最短的两块进行合并。每次合并的代价是两个面包的长度之和。通过这种方式，可以确保每次合并的代价最小，从而最终达到最小的总花费。

为了实现这个过程，我们可以使用一个优先队列（最小堆）来维护当前所有待合并的面包。每次从队列中取出两个长度最小的面包进行合并，并将合并后的新面包重新加入到队列中。如此反复，直到队列中只剩下一个面包。

接下来，考虑如何处理“每个孩子 $i$ 必须收到一个长度正好为 $A_i$ 的面包”这个要求。如果原始面包长度 $L$ 大于这些长度之和，则将多余的部分 $L - \sum A_i$ 也加入到队列中。代表“多出来的部分”也需要被单独分割出来。

本题的 AC 代码如下：

#include <iostream>
#include <queue>
using namespace std;
#define int long long

int L, N, sum;
priority_queue<int, vector<int>, greater<int> > que;

void solve(){
    int total = 0;
    bool flag = 1;
    if (L != sum)
        que.push(L - sum);
    while(que.size() > 1){
        int a = que.top(); que.pop();
        int b = que.top(); que.pop();
        total += a + b;
        que.push(a + b);
    }
    cout << total << endl;
    return ;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> N >> L;
    for (int i=1, t; i<=N; i++){
        cin >> t;
        sum += t;
        que.push(t);
    }
    solve();
    return 0;
}