P13500 「Cfz Round 6」Kyu-kurarin

ちゃんと笑えなきゃね 必须保持笑容才行啊 大した取り柄も無いから 除此之外我一无所有

Yuki 是一位魔法少女，她有着 $n$ 块冰，其中第 $i$ 块冰的质量为 $a_i$。 对于所有正整数 $t$： - 第 $(t-0.5)$ 秒，Yuki 可以对最多 $k$ 块不同的**未完全融化**（即质量大于 $0$）的冰使用魔法，使它们的质量都增加 $1$； - 第 $t$ 秒，每块冰都会发生融化，它们的质量都会减少 $1$。 Yuki 需要你求出最大的非负整数 $s$，满足在第 $s$ 秒及第 $s$ 秒前，Yuki 可以使用她的魔法从而使得每块冰都没有完全融化（即满足每块冰的质量始终大于 $0$）。

第一行包含两个正整数 $n,k$。 第二行包含 $n$ 个正整数 $a_1,\dots,a_n$。

输出一行，包含一个非负整数，表示最大的非负整数 $s$，满足在第 $s$ 秒及第 $s$ 秒前，Yuki 可以使用她的魔法从而使得每块冰都没有完全融化（即满足每块冰的质量始终大于 $0$）。

### 样例 1 解释 Yuki 可以这样使用魔法： - 第 $0.5$ 秒时，Yuki 对第 $2$ 块冰使用魔法，此时 $3$ 块冰的质量分别为 $3,2,4$； - 第 $1$ 秒时，所有冰发生融化，此时 $3$ 块冰的质量分别为 $2,1,3$； - 第 $1.5$ 秒时，Yuki 对第 $2$ 块冰使用魔法，此时 $3$ 块冰的质量分别为 $2,2,3$； - 第 $2$ 秒时，所有冰发生融化，此时 $3$ 块冰的质量分别为 $1,1,2$。 容易证明，在第 $3$ 秒时，一定有冰会完全融化，所以最大的满足要求的正整数 $s$ 等于 $2$。 ### 样例 2 见题目附件中的 $\textbf{\textit{ice/ice2.in}}$ 与 $\textbf{\textit{ice/ice2.ans}}$。 该组样例满足测试点 $3$ 的限制。 ### 样例 3 见题目附件中的 $\textbf{\textit{ice/ice3.in}}$ 与 $\textbf{\textit{ice/ice3.ans}}$。 该组样例满足测试点 $5$ 的限制。 ### 样例 4 见题目附件中的 $\textbf{\textit{ice/ice4.in}}$ 与 $\textbf{\textit{ice/ice4.ans}}$。 该组样例满足测试点 $6$ 的限制。 ### 样例 5 见题目附件中的 $\textbf{\textit{ice/ice5.in}}$ 与 $\textbf{\textit{ice/ice5.ans}}$。 该组样例满足测试点 $9$ 的限制。 ### 样例 6 见题目附件中的 $\textbf{\textit{ice/ice6.in}}$ 与 $\textbf{\textit{ice/ice6.ans}}$。 该组样例满足测试点 $10$ 的限制。 ### 数据范围 对于所有测试数据： - $2 \le n \le 10^6$； - $1 \le k \le n-1$； - $1 \le a_i \le 10^6$。 |测试点编号|$n\le$|$k\le$|$a_i \le$|特殊性质| |:---:|:---:|:---:|:---:|:---:| |$1$|$2$|$1$|$10^6$|否| |$2$|$10^3$|$1$|$10^3$|是| |$3$|$10^3$|$1$|$10^3$|否| |$4$|$10^3$|$n-1$|$10^3$|是| |$5$|$10^3$|$n-1$|$10^3$|否| |$6$|$10^6$|$1$|$10^6$|是| |$7$|$10^6$|$1$|$10^6$|否| |$8$|$10^6$|$10$|$10^6$|否| |$9$|$10^6$|$n-1$|$10^6$|是| |$10$|$10^6$|$n-1$|$10^6$|否| 特殊性质：保证所有冰的质量相等，即 $a_1=a_2=\dots=a_n$。