Codeforces Round #616 (Div. 2) C. Mind Control

被卡两小时直接自闭，还是想太多了。传送门

题意： 给你一个长度为 $n$n的序列，共有 $n$n个人来取数，每次只能在序列当前的首尾取数。你排在第 $m$m位，同时你有 $k$k次控制别人选择数的机会，现在问你合理操作后至少可以得到的最大值为多少？

题解： 到你选择的时候，区间长度为 $n-m+1$n−m+1，前 $m-1$m−1个人选择数的情况才会对你选择的数有影响，由于控制次数的限制，故最多有效限制次数为 $valid=min(k,m-1)$valid=min(k,m−1)，数据范围允许暴力，故枚举区间即可。

具体细节：
预处理出所有长度为 $n-m+1$n−m+1的区间最大值，由于最多有效限制次数为 $valid$valid，我们枚举取左端的数的个数为 $l$l，那么 $l\in [0,valid]$l∈[0,valid]，故取右端的数的个数为 $r=k-l$r=k−l。然后枚举区间 $[l,r]$[l,r]，取得最小值（认为在你之前取数且不受控制的人会尽可能使你取到的值小），这 $valid+1$valid+1个结果的最大值即答案。

代码：

#include<bits/stdc++.h>
using namespace std;

const int N = 3510;
int q[N], Ma[N], n, m, k, T;

int main()
{
	scanf("%d", &T);
	while(T--){ 
		scanf("%d%d%d", &n, &m, &k);
		for(int i = 1; i <= n; i++) scanf("%d", &q[i]);
		
		int len = n - m + 1;
		for(int i = 1; i <= n - len + 1; i++) Ma[i] = max(q[i], q[i + len - 1]);
		
		k = min(m - 1, k);
		int res = 0; 
		for(int l = 0; l <= k; l++) {
			int disr = k - l, ans = 0x3f3f3f3f;
			int r = n - disr - (len - 1);
			for(int i = l + 1; i <= r; i++) ans = min(ans, Ma[i]);
			res = max(res, ans);
		} 
		printf("%d\n", res);
	} 
	return 0;
}