#CF2272C. Yet Another Black Cell Problem

Yet Another Black Cell Problem

题目描述

受此题启发。

有一条纸带,被划分为从左到右编号为 00 到 10910^9 的格子。初始时所有格子都是白色的。

给定一个长度为 nn 的数组 aa,包含 nn 个格子的下标。我们想把这 nn 个格子都涂成黑色。

给定一个整数 xx,你可以选择一个整数 yy 满足 0≤y≤x0 \le y \le x,然后任意选择 yy 个不在 aa 中的格子。我们也想把这 yy 个选中的格子涂成黑色,同时保持所有未选中的格子为白色。

你可以执行以下操作任意次数:

  • 选择两个不同的格子 ii 和 jj,满足 1≤∣i−j∣≤k1 \le |i-j| \le k,并将它们涂成黑色,无论它们原来是黑色还是白色。

求最小的 kk 值,使得能够将所有需要涂黑的格子涂成黑色,同时保持其他格子为白色。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 tt(1≤t≤1041 \le t \le 10^4)。接下来是每个测试用例的描述。

每个测试用例的第一行包含两个整数 nn 和 xx(2≤n≤2⋅1052\leq n\leq 2\cdot 10^5,0≤x≤n0\leq x\leq n)。

第二行包含 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n(0≤ai≤1090\leq a_i\leq 10^{9})。保证对所有 1≤i<n1 \leq i \lt n,都有 ai<ai+1a_i \lt a_{i+1}。

保证所有测试用例的 nn 之和不超过 2⋅1052\cdot 10^5。

输出格式

对于每个测试用例,输出一个整数——使得能够将所有需要涂黑的格子涂成黑色同时保持其他格子为白色的最小 kk 值。

样例

4
2 0
1 3
2 1
1 3
3 1
2 5 7
10 2
0 6 8 10 13 14 16 19 25 31
2
1
2
3

说明

在第一个样例中,因为 x=0x=0,我们不能将 11 和 33 以外的任何格子涂成黑色。因此最优做法是令 k=2k=2,并在第一次操作中选择 i=1i=1、j=3j=3。

在第二个样例中,我们可以令 k=1k=1,这是可用的最小值。我们首先选择 i=1i=1、j=2j=2 进行涂色,然后选择 i=2i=2、j=3j=3 进行涂色。此后,格子 1,2,31,2,3 都被涂成黑色,只有格子 22 不在给定列表中,这满足 x=1x=1 的条件。

来源

导入自 Codeforces — Codeforces Round 1130 (Div. 2)。