拿石子

Background

这道题不可能有低于 $\operatorname{O}(n^{2}\log n)$ 的做法。——匿名用户 1

$\operatorname{O}(1)$ 秒了！——匿名用户 2

Description

兹有 $n$ 堆石子，第 $i$ 堆石子有 $a_{i}$ 个，定义一次操作为：

• 任选 $k$ 堆石子，从每堆石子中各拿走 $1$ 个，即置 $a_{i}\leftarrow a_{i}-1$。

最大化操作次数。

Input

第一行两个整数 $n,k$，第二行 $n$ 个整数，第 $i$ 个整数表示 $a_{i}$。

3 2
1 2 3

Output

一个整数，表示答案。

3

Hint

对于 $100\%$ 的数据，$1 \leqslant k \leqslant n \leqslant 5 \times 10^{5}$，$0 \leqslant a_{i} \leqslant 5 \times 10^{5}$，且 $\sum a_{i} \leqslant 10^{9}$。

Notes

二分答案，考虑能否进行 $x$ 次操作。

由于每堆石子只能取 $x$ 次，置 $a_{i}\leftarrow \min\lbrace a_{i},x \rbrace$，如果剩下的石子总数 $\geqslant kx$，则一定可行。

具体的操作方案是，将不足 $x$ 个石子的堆用另一堆补为 $x$ 个，最终将补成 $k$ 堆，每堆有 $x$ 个石子，每次每堆拿一个即可。

直接在线段树上二分，时间复杂度优化为 $\Theta(n\log n)$。