[AtCoder ARC098]E - Range Minimum Queries

Posted on
AtCoder ARC098 E

E - Range Minimum Queries

Time limit : 2sec / Memory limit : 1024MB
Score : 600 points

Problem Statement

You are given an integer sequence $A$ of length $N$ and an integer $K$. You will perform the following operation on this sequence $Q$ times:

  • Choose a contiguous subsequence of length $K$, then remove the smallest element among the $K$ elements contained in the chosen subsequence (if there are multiple such elements, choose one of them as you like).

Let $X$ and $Y$ be the values of the largest and smallest element removed in the $Q$ operations. You would like $X−Y$ to be as small as possible. Find the smallest possible value of $X−Y$ when the $Q$ operations are performed optimally.

Constraints

$1≤N≤2000$
$1≤K≤N$
$1≤Q≤N−K+1$
$1≤A_i≤10^9$
All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$ $K$ $Q$
$A_1$ $A_2$ … $A_N$

Output

Print the smallest possible value of $X−Y$.

Samples

Input Output
5 3 2
4 3 1 5 2		 1
10 1 6
1 1 2 3 5 8 13 21 34 55		 7
11 7 5
24979445 861648772 623690081 433933447 476190629 262703497 211047202 971407775 628894325 731963982 822804784		 451211184

In the first operation, whichever contiguous subsequence of length 3 we choose, the minimum element in it is $1$. Thus, the first operation removes $A_3=1$ and now we have $A=(4,3,5,2)$. In the second operation, it is optimal to choose $(A_2,A_3,A_4)=(3,5,2)$ as the contiguous subsequence of length $3$ and remove $A_4=2$. In this case, the largest element removed is $2$, and the smallest is $1$, so their difference is $2−1=1$.

解题思路

如果从正面来想，最大值 $X$ 和最小值 $Y$ 都在变，所以不好解决。
于是我们可以固定最小值 $Y$，每次找符合要求的最小的 $X$ 就行了。
具体来说，从小到大枚举最小值 $Y$，对于每次枚举的 $Y$：我们可以找到一些区间，满足区间长度 $len$ 大于等于 $K$ 并且区间内的所有数都大于等于 $Y$，于是这个区间内的前 $len - K + 1$ 小都有可能被选进答案，记录下这些可能值后，排序就可以找到对于当前的 $Y$ 最小的 $X$ 是多少，用 $X-Y$ 更新 $ans$ 即可。

时间复杂度：枚举是 $O(N)$ 的，每次枚举中查找可能值+排序是 $O(N＋N\log N)$的，所以总复杂度是 $O(N^2\log N)$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<cstdio>
#include<algorithm>

using namespace std;

const int N = 2005;
int n, k, q, a[N], ans = 1e9+5, t[N], b[N], c[N];

void cal(int mn){
	int l = 1, r = 1;
	b[0] = 0;
	while(l <= n){
		c[0] = 0;
		while(a[l] < mn && l <= n)	l++;
		r = l;
		while(a[r] >= mn && r <= n)	r++;
		for(int i = l; i < r && i <= n; i++)
			c[++c[0]] = a[i];
		if(c[0] >= k){
			sort(c+1, c+c[0]+1);
			for(int i = 1; i <= c[0] - k + 1; i++)
				b[++b[0]] = c[i];
		}
		l = r;
	}
	sort(b+1, b+b[0]+1);
	if(b[0] >= q)	ans = min(ans, b[q] - b[1]);
}

int main(){
	scanf("%d%d%d", &n, &k, &q);
	for(int i = 1; i <= n; i++){
		scanf("%d", &a[i]);
		t[i] = a[i];
	}
	sort(t+1, t+n+1);
	for(int i = 1; i <= n; i++)
		cal(t[i]);
	printf("%d\n", ans);
	return 0;
}