CF1712D Empty Graph

——你有什么愿望吗？ ——我希望人们不要再互相送数组了。 O_o 和 Another Young Boy 有一个长度为 $n$ 的正整数数组 $a_1,a_2,\ldots,a_n$ 从天而降，同时还有一个正整数 $k$，满足 $k \le n$。 你最多可以进行 $k$ 次如下操作： - 选择一个下标 $1 \le i \le n$ 和一个整数 $1 \le x \le 10^9$，然后将 $a_i$ 赋值为 $x$（即 $a_i := x$）。 接下来，你需要构建一个有 $n$ 个顶点的[完全](https://en.wikipedia.org/wiki/Complete_graph)无向带权图，顶点编号为 $1$ 到 $n$。对于每一条边 $(l, r)$（$1 \le l < r \le n$），其权值为 $\min(a_l, a_{l+1}, \ldots, a_r)$。 你需要在最多进行 $k$ 次操作后，求出最终得到的图的最大可能直径。 图的直径定义为 $\max\limits_{1 \le u < v \le n}{\operatorname{d}(u, v)}$，其中 $\operatorname{d}(u, v)$ 表示顶点 $u$ 和 $v$ 之间的最短路径长度。

每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每组测试用例的第一行包含两个整数 $n$ 和 $k$（$2 \le n \le 10^5$，$1 \le k \le n$）。 每组测试用例的第二行包含 $n$ 个正整数 $a_1,a_2,\ldots,a_n$（$1 \le a_i \le 10^9$）。 保证所有测试用例中 $n$ 的总和不超过 $10^5$。

对于每组测试用例，输出一个整数，表示在最多进行 $k$ 次操作后，图的最大可能直径。

在第一个测试用例中，一个最优的数组是 $[2,4,5]$。 基于该数组构建的图如下：  $\operatorname{d}(1, 2) = \operatorname{d}(1, 3) = 2$，$\operatorname{d}(2, 3) = 4$，所以直径为 $\max(2,2,4) = 4$。 由 ChatGPT 4.1 翻译