AT_abc252_f [ABC252F] Bread

题目描述

有一块长度为 $L$ 的面包，需要将其分给 $N$ 个孩子。第 $i$ 个孩子（$1\leq i\leq N$）想要长度为 $A_i$ 的面包。

高桥君可以重复进行如下操作，将长度为 $A_1,A_2,\ldots,A_N$ 的面包切出来并分发：

选择一块长度为 $k$ 的面包和一个整数 $x$，其中 $1\leq x\leq k-1$。将选中的面包切分为长度为 $x$ 和 $k-x$ 的两块面包。
无论 $x$ 取何值，每次切割的花费都是 $k$。

每个孩子只能分到一块长度恰好为 $A_i$ 的面包，剩余的面包可以有任意多块，不需要分配。

请你求出，为了分给所有孩子面包所需的最小总花费。

输入格式

输入通过标准输入给出，格式如下：

$N$ $L$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

输出分给所有孩子面包所需的最小总花费。

输入输出样例 #1

输入 #1

5 7
1 2 1 2 1

输出 #1

16

输入输出样例 #2

输入 #2

3 1000000000000000
1000000000 1000000000 1000000000

输出 #2

1000005000000000

说明/提示

限制条件

• $2\leq N\leq 2\times 10^5$
• $1\leq A_i\leq 10^9$
• $A_1+A_2+\cdots+A_N\leq L\leq 10^{15}$
• 所有输入均为整数

样例解释 1

高桥君可以按如下方式切分面包并分发：

• 选择长度为 $7$ 的面包和整数 $x=3$。面包被切分为长度为 $3$ 和 $4$ 的两块面包。（花费 $7$）
• 选择长度为 $3$ 的面包和整数 $x=1$。面包被切分为长度为 $1$ 和 $2$ 的两块面包。将长度为 $1$ 的面包分给第 $1$ 个孩子。（花费 $3$）
• 选择长度为 $2$ 的面包和整数 $x=1$。面包被切分为两个长度为 $1$ 的面包。将这两块面包分给第 $3$ 和第 $5$ 个孩子。（花费 $2$）
• 选择长度为 $4$ 的面包和整数 $x=2$。面包被切分为两个长度为 $2$ 的面包。将这两块面包分给第 $2$ 和第 $4$ 个孩子。（花费 $4$）

此时，总花费为 $7+3+2+4=16$，这是最小值。没有剩余面包。

样例解释 2

请注意，每个孩子分到的面包长度必须恰好为 $A_i$。

由 ChatGPT 4.1 翻译