Bread

题目描述

我们有一条长度为 $L$ 的面包，需要把它切分并分配给 $N$ 个孩子。
第 $i$ 个孩子 $(1\leq i\leq N)$ 想要长度为 $A_i$ 的面包片。 现在，高桥将重复下面的操作，把面包切成供孩子们的长度 $A_1, A_2, \ldots, A_N$。

选择一条长度为 $k$ 的面包和一个介于 $1$ 到 $k-1$（含）之间的整数 $x$。把这条面包切成长度为 $x$ 和 $k-x$ 的两条面包。
无论 $x$ 的值如何，这一操作的代价都是 $k$。

每个孩子 $i$ 必须得到长度恰好为 $A_i$ 的面包片，但允许有些面包片不分发出去。 求把面包分给所有孩子所需的最小代价。

输入格式

输入从标准输入按以下格式给出： $N$ $L$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

输出把面包分给所有孩子所需的最小代价。

5 7
1 2 1 2 1

16

3 1000000000000000
1000000000 1000000000 1000000000

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}$ 输入中的所有数值均为整数。高桥可以按如下方式为孩子们切分面包。

选择长度为 $7$ 的面包并取 $x=3$，将其切成长度为 $3$ 和 $4$ 的两块，代价为 $7$。 选择长度为 $3$ 的面包并取 $x=1$，将其切成长度为 $1$ 和 $2$，代价为 $3$。把前者给第 $1$ 个孩子。 选择长度为 $2$ 的面包并取 $x=1$，将其切成两块长度为 $1$ 的面包，代价为 $2$。把它们分别给第 $3$ 和第 $5$ 个孩子。 选择长度为 $4$ 的面包并取 $x=2$，将其切成两块长度为 $2$ 的面包，代价为 $4$。把它们分别给第 $2$ 和第 $4$ 个孩子。

这样产生的总代价为 $7+3+2+4=16$，这是可能的最小值。 不会有多余的面包片。
注意每个孩子 $i$ 必须得到长度恰好为 $A_i$ 的面包片。

标签: AtCoder|abc252F

来源

AtCoder|abc252F