#P17761. game

game

题目描述

小 P 给了小 Q 排成一排的 nn 个球,其中第 ii 个球上写着一个正整数 aia_i,初始时有另一个长度为 mm 的数列 bb,其中所有的元素均为 00。

小 P 和小 Q 要用这 nn 个球来做游戏,游戏可以分为两个阶段:

  • 小 Q 进行 mm 次操作,在一次操作中,小 Q 需要选择连续的 kk 个球,假设这 kk 个球中写的最小数为 xx,则小 Q 可以选择这 kk 个球中的任意一个写着 xx 的球删除,在删除一个球后,其左右两侧的球会自动靠在一起,如果这是第 ii 次操作,则将 bib_i 赋值为 xx。
  • 小 P 选择 bb 中的两个元素 x,yx, y(不一定要不同),这局游戏的得分为 xx 与 yy 的差的绝对值。

小 P 想让游戏的得分最大,而小 Q 想让得分最小,你想知道在两人均采取最优策略的前提下,游戏的得分最终是多少。

输入格式

本题有多组测试数据。输入的第一行两个整数 c,Tc, T 表示测试点编号和测试数据组数,特别的,在样例中,c=0c = 0。

对于每组测试数据,

  • 第一行三个正整数 n,m,kn, m, k,表示球的个数,小 Q 操作的次数和一次操作选择球的个数。
  • 第二行一行 nn 个正整数,其中第 ii 个正整数为 aia_i,表示初始时从左往右第 ii 个球上所写的数字。

输入数据保证小 Q\mathbf{Q} 能够进行至少 m\boldsymbol{m} 次操作,即 m≤n−k+1\boldsymbol{m \le n - k + 1}。

输出格式

对于每组测试数据输出一行一个整数,表示最终游戏的分数。

样例 1

0 2
5 2 3
4 3 1 5 2
7 3 2
7 1 3 8 9 7 9
1
2

样例解释 1

对于该组样例中的第一组测试数据,初始时有 55 个球从左往右分别写着 4,3,1,5,24, 3, 1, 5, 2,数列 b={0,0}b = \{0, 0\},一种可能的游戏过程如下:

  • 在小 Q 的第 11 次操作中,小 Q 选择第 33 个球至第 55 个球,此时 x=1x = 1,操作后球分别写着 4,3,5,24, 3, 5, 2,此时 b={1,0}b = \{1, 0\};
  • 在小 Q 的第 22 次操作中,小 Q 选择第 22 个球至第 44 个球,此时 x=2x = 2,操作后球分别写着 4,3,54, 3, 5,此时 b={1,2}b = \{1, 2\};
  • 小 P 选择 x=b1=1,y=b2=2x = b_1 = 1, y = b_2 = 2,此时 aa 与 bb 的差的绝对值为 11,故这局游戏的得分为 11。

可以证明这是一种在最优策略下可能的游戏过程之一。

数据范围与提示

设 ∑n\sum n 为单个测试点内所有测试数据 nn 的和。对于所有测试数据:

  • 1≤T≤2×1061 \le T \le 2 \times 10^6;
  • 1≤k≤n≤1051 \le k \le n \le 10^5,1≤∑n≤2×1061 \le \sum n \le 2\times10^6;
  • 1≤m≤n−k+11 \le m \le n - k + 1,1≤ai≤1091 \le a_i \le 10^9。
测试点编号 n≤n \le ∑n≤\sum n \le 特殊性质
11 55 100100 无
2∼42 \sim 4 1515 20002000
5∼75 \sim 7 100100
8∼98 \sim 9 500500
10∼1110 \sim 11 10001000 10410^4 A
1212 B
1313 C
14∼1514 \sim 15 无
1616 5×1045 \times 10^4 5×1055 \times 10^5 A
17∼1817 \sim 18 B
19∼2019 \sim 20 C
21∼2321 \sim 23 无
24∼2524 \sim 25 10510^5 2×1062\times 10^6
  • 特殊性质 A:m=n−k+1m = n - k + 1;
  • 特殊性质 B:ai≤2a_i \le 2;
  • 特殊性质 C:ai≤ai+1(1≤i<n)a_i \le a_{i+1} (1 \le i < n)。