好眼熟啊……
题意
有一个长度为 \(l\) 的扩散性百万甜面包要分给 \(n\) 个小朋友，第 \(i\) 个小朋友想要一根长度为 \(a_i\) 的面包，保证 \(\sum\limits_{1\leqslant i \leqslant n} a_i \leqslant l\)，注意是小于等于，即面包可以有剩余。
你可以切面包若干次，每次切面包都需要花费一定力气，每次选择一个长度为 \(x\) 的面包，可以将其切成两块长度分别为 \(a\) 和 \(b\) 的面包，需要满足：\(1 \leqslant a,b \leqslant x\) 且 \(a + b = x\)，花费力气为 \(x\)。
求满足每个小朋友的愿望最少需要多少力气。
思路
正着来做，你并不知道每次该怎么切，所以考虑反着做。
既然是反着做，那么切面包就可以看作是把两个长度分别为 \(a\) 和 \(b\) 的面包合并成一个长度为 \(a + b\) 的面包，耗费力气 \(a + b\)。
欸，这不就是合并果子吗？
但是需要注意的是，这里可能还有一个长度为 \(l - \sum\limits_{1\leqslant i \leqslant n} a_i\) 的面包，我们肯定不会去切这块面包，所以这里必然只是一根，需要注意。
按照合并果子的贪心做法，每次选择两个较小的面包合在一起，计算答案即可。
记得开long long。
总时间复杂度：\(O(n \log n)\)。
代码
点击查看代码
#include <iostream>
#include <queue>
using namespace std;
using ll = long long;
int n, x;
ll l, sum, ans, a;
priority_queue<ll, vector<ll>, greater<ll>> pq; // 小根堆维护长度最小的面包
int main () {
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> l;
for (int i = 1; i <= n; i++) {
cin >> x, sum += x, pq.push(x);
}
if (sum < l) { // 特殊处理剩下的那一根面包
pq.push(l - sum);
}
while (pq.size() > 1) { // 合并果子，不用多说
a = pq.top(), pq.pop(), a += pq.top(), pq.pop(), ans += a, pq.push(a);
}
cout << ans;
return 0;
}