官方题解｜分面包

题目解析

1. 首先考虑 $L=A_1+A_2+\ldots +A_N$ 的情况：

反转问题为：“使用 $x + y$ 的成本将原本长度为 $x$ 和 $y$ 的面包拼接在一起，求将面包 $A_1, \ldots, A_N$ 合并为一个面包的最小费用。”

这个问题和原问题等价。
在这里，原问题的最小费用等于在多重集 $S=\{ A_1,A_2,\ldots,A_N \}$ 上重复以下操作 $(N-1)$ 次的成本之和：

• 令 $s_1$ 和 $s_2$ 为 $S$ 中最小的两个元素。以 $s_1+s_2$ 的成本将长度为 $s_1$ 和 $s_2$ 的两条面包拼接在一起。
• 从 $S$ 中删除 $s_1$ 和 $s_2$，并将 $s_1+s_2$ 插入到 $S$ 中。

由于每次操作后 $S$ 的元素数量减少 $1$，显然完成以上操作后，$S$ 只会剩下一个元素。

2. 考虑 $L \gt A_1+A_2+\ldots +A_N$ 的情况：

对于 $L > A_1+A_2+\cdots+A_N$，我们可以令 $L = A_1 + A_2 + \cdots + A_N + X$。
将剩余的部分当作一条面包，反转问题为：“使用 $x + y$ 的成本将原本长度为 $x$ 和 $y$ 的面包拼接在一起，求将面包 $A_1, \ldots, A_N, X$ 合并为一条面包的最小费用。”
这个问题同样可以使用上述的方法解决。

AC代码

C++ AC代码：

#include <bits/stdc++.h>

using i64 = long long;

int main() {
    i64 n, m;
    std::cin >> n >> m;
    std::vector<i64> a(n);
    for (auto &x : a) std::cin >> x;
    i64 sum = std::accumulate(a.begin(), a.end(), 0LL);
    std::priority_queue<i64,
        std::vector<i64>,
        std::greater<i64>> pq(a.begin(), a.end());
    if (sum < m) pq.push(m - sum);
    i64 res = 0;
    while (pq.size() > 1) {
        auto u = pq.top(); pq.pop();
        auto v = pq.top(); pq.pop();
        pq.emplace(u + v);
        res += u + v;
    }
    std::cout << res << '\n';
    return 0;
}

Python AC代码：

import heapq
n, m = map(int, input().split())
a = list(map(int, input().split()))
tot = sum(a)
if tot < m:
    a.append(m - tot)
heapq.heapify(a)
res = 0
while len(a) > 1:
    u = heapq.heappop(a)
    v = heapq.heappop(a)
    heapq.heappush(a, u + v)
    res += u + v
print(res)

复杂度分析

使用「有序集合」或「优先队列」等数据结构充当集合 $S$，在 $\mathrm{O}(N\log{N})$ 的时间复杂度完成处理。