P15543 [CCC 2026 S4] Minecarts

史蒂夫有 $N$ 辆矿车，编号从 $1$ 到 $N$，在轨道上从左到右排成一列。最初，第 $i$ 辆矿车中有 $a_i$ 颗宝石。 史蒂夫希望矿车排成一列，使得从左到右每辆矿车中的宝石数量非递减。为此，他计划在所有矿车的右侧修建一条从主轨道分岔出去的侧线。史蒂夫可以将侧线左侧的矿车移入侧线，允许其左侧的其他矿车在主轨道上从它旁边驶过。移入侧线的矿车可以一次一辆地移回主轨道：侧线上的矿车将移回至侧线的左侧，并且位于侧线左侧所有其他矿车的右侧。最后移入侧线的矿车必须是最先移出的矿车：也就是说，侧线遵循后进先出的原则。侧线可以使用任意多次。最后，一旦矿车被移动到侧线的右侧，它就不能再向左移动。以下是从初始位置开始用 5 辆矿车可以进行的移动序列示例： :::align{center}   ::: 史蒂夫有 $K$ 颗备用宝石，他可以将任意数量的备用宝石放入 **空** 矿车中。史蒂夫尚未修建侧线，他希望限制侧线容量以节省工作量。具有特定容量的侧线最多只能存放相应数量的矿车。例如，如果侧线容量为 1，我们就无法进行上图中的移动，因为那至少需要容量为 2。假设史蒂夫以最优方式将备用宝石放入矿车，那么需要修建的侧线最小容量是多少？

输入的第一行包含两个空格分隔的整数 $N$ 和 $K$（$1 \le N \le 3 \times 10^5$，$0 \le K \le 10^{12}$）。 下一行包含 $N$ 个整数 $a_1, \dots, a_n$（$0 \le a_i \le 10^6$），其中第 $i$ 个整数表示第 $i$ 辆矿车中的宝石数量。

输出一个整数，在史蒂夫以最优方式将最多 $K$ 颗宝石分配到空矿车中的情况下，需要修建的侧线的最小容量。

#### 样例输入 1 的输出解释 一种最优分配是将 6 颗备用宝石放入 2 号矿车，将 7 颗备用宝石放入 4 号矿车。注意这种分配并未使用所有备用宝石。 然后我们可以修建一条容量为 1 的侧线。我们可以按如下步骤将矿车排列成非递减顺序： 1. 将 4 号矿车移动到侧线右侧 2. 将 3 号矿车移入侧线 3. 将 2 号矿车移动到侧线右侧 4. 将 1 号矿车移动到侧线右侧 5. 将 3 号矿车移出侧线 6. 将 3 号矿车移动到侧线右侧 #### 样例输入 2 的输出解释 一种最优分配是将全部 8 颗备用宝石放入 4 号矿车。 然后我们可以修建一条容量为 2 的侧线。我们可以按如下步骤将矿车排列成非递减顺序： 1. 将 4 号矿车移动到侧线右侧 2. 将 3 号矿车移入侧线 3. 将 2 号矿车移入侧线 4. 将 1 号矿车移动到侧线右侧 5. 将 2 号矿车移出侧线 6. 将 3 号矿车移出侧线 7. 将 3 号矿车移动到侧线右侧 8. 将 2 号矿车移动到侧线右侧 #### 样例输入 3 的输出解释 由于没有空矿车，只有一种可能的备用宝石分配方式：不使用任何备用宝石。 然后我们可以修建一条容量为 3 的侧线。我们可以按如下步骤将矿车排列成非递减顺序： 1. 将 4 号矿车移入侧线 2. 将 3 号矿车移入侧线 3. 将 2 号矿车移入侧线 4. 将 1 号矿车移动到侧线右侧 5. 将 2 号矿车移出侧线，然后移动到侧线右侧 6. 将 3 号矿车移出侧线，然后移动到侧线右侧 7. 将 4 号矿车移出侧线，然后移动到侧线右侧 下表展示了 15 分的分布情况： | 分值 | $N$ 的范围 | $K$ 的范围 | |:-:|:-:|:-:| | 2 分 | $1 \le N \le 5000$ | $K = 0$ | | 2 分 | $1 \le N \le 5000$ | $K = 10^{12}$ | | 2 分 | $1 \le N \le 5000$ | $0 \le K \le 10^{12}$ | | 3 分 | $1 \le N \le 3 \times 10^5$ | $K = 0$ | | 3 分 | $1 \le N \le 3 \times 10^5$ | $K = 10^{12}$ | | 3 分 | $1 \le N \le 3 \times 10^5$ | $0 \le K \le 10^{12}$ | 翻译由 DeepSeek 完成