← 返回题目列表

Codeforces · 1712/D

D. 空图

中文机器翻译题面 查看原题

一组 $$$n$$$ 正整数 $$$a_1,a_2,\ldots,a_n$$$ 从天而降,还有一个正整数 $$$k \le n$$$。

您最多可以应用以下操作 $$$k$$$ 次:

- 选择一个索引 $$$1 \le i \le n$$$ 和一个整数 $$$1 \le x \le 10^9$$$。然后执行 $$$a_i := x$$$ (将 $$$x$$$ 分配给 $$$a_i$$$)。

然后构建一个完整的无向加权图,其中 $$$n$$$ 顶点编号为 $$$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$$$ 操作后图形的最大可能直径。

示例

输入 #1

6
3 1
2 4 1
3 2
1 9 84
3 1
10 2 6
3 2
179 17 1000000000
2 1
5 9
2 2
4 2

输出 #1

4
168
10
1000000000
9
1000000000

注意

在第一个测试用例中,最佳数组之一是 $$$[2,4,5]$$$。

在此数组上构建的图:

$$$\operatorname{d}(1, 2) = \operatorname{d}(1, 3) = 2$$$ 和 $$$\operatorname{d}(2, 3) = 4$$$,因此直径等于 $$$\max(2,2,4) = 4$$$。