题目描述
小 P 给了小 Q 排成一排的 n 个球,其中第 i 个球上写着一个正整数 ai,初始时有另一个长度为 m 的数列 b,其中所有的元素均为 0。
小 P 和小 Q 要用这 n 个球来做游戏,游戏可以分为两个阶段:
- 小 Q 进行 m 次操作,在一次操作中,小 Q 需要选择连续的 k 个球,假设这 k 个球中写的最小数为 x,则小 Q 可以选择这 k 个球中的任意一个写着 x 的球删除,在删除一个球后,其左右两侧的球会自动靠在一起,如果这是第 i 次操作,则将 bi 赋值为 x。
- 小 P 选择 b 中的两个元素 x,y(不一定要不同),这局游戏的得分为 x 与 y 的差的绝对值。
小 P 想让游戏的得分最大,而小 Q 想让得分最小,你想知道在两人均采取最优策略的前提下,游戏的得分最终是多少。
输入格式
本题有多组测试数据。输入的第一行两个整数 c,T 表示测试点编号和测试数据组数,特别的,在样例中,c=0。
对于每组测试数据,
- 第一行三个正整数 n,m,k,表示球的个数,小 Q 操作的次数和一次操作选择球的个数。
- 第二行一行 n 个正整数,其中第 i 个正整数为 ai,表示初始时从左往右第 i 个球上所写的数字。
输入数据保证小 Q 能够进行至少 m 次操作,即 m≤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
对于该组样例中的第一组测试数据,初始时有 5 个球从左往右分别写着 4,3,1,5,2,数列 b={0,0},一种可能的游戏过程如下:
- 在小 Q 的第 1 次操作中,小 Q 选择第 3 个球至第 5 个球,此时 x=1,操作后球分别写着 4,3,5,2,此时 b={1,0};
- 在小 Q 的第 2 次操作中,小 Q 选择第 2 个球至第 4 个球,此时 x=2,操作后球分别写着 4,3,5,此时 b={1,2};
- 小 P 选择 x=b1=1,y=b2=2,此时 a 与 b 的差的绝对值为 1,故这局游戏的得分为 1。
可以证明这是一种在最优策略下可能的游戏过程之一。
数据范围与提示
设 ∑n 为单个测试点内所有测试数据 n 的和。对于所有测试数据:
- 1≤T≤2×106;
- 1≤k≤n≤105,1≤∑n≤2×106;
- 1≤m≤n−k+1,1≤ai≤109。
| 测试点编号 |
n≤ |
∑n≤ |
特殊性质 |
| 1 |
5 |
100 |
无 |
| 2∼4 |
15 |
2000 |
| 5∼7 |
100 |
| 8∼9 |
500 |
| 10∼11 |
1000 |
104 |
A |
| 12 |
B |
| 13 |
C |
| 14∼15 |
无 |
| 16 |
5×104 |
5×105 |
A |
| 17∼18 |
B |
| 19∼20 |
C |
| 21∼23 |
无 |
| 24∼25 |
105 |
2×106 |
- 特殊性质 A:m=n−k+1;
- 特殊性质 B:ai≤2;
- 特殊性质 C:ai≤ai+1(1≤i<n)。