Codeforces_Round_616_(Div_2)_C题
Codeforces_Round_616_(Div_2)_C题
题目大意
有$n$个人，有$n$个数字组成序列$a$， 你当前站在第$m$个位置，每一次每个人从这$n$个数字的头或者尾拿走一个数字，一开始你可以说服在拿的时候$k$个人拿首还是拿尾，其他人会任意拿，说服那些人拿首还是拿尾要一开始就确定好，中间不能变。最大化通过控制能确定拿到的值
题解
注：题解描述下标从1开始，代码中下标从0开始
显然对于后$n-m$个人，他们怎么拿对结果都没有影响。那么可以说服的人数$k = min(k, m-1)$，假设说服$x$个人拿首，有$y$个没说服的人拿了首，显然$x \in [0, k]，y \in [0, m-1-k]$，那么容易知道第$m$个人拿的时候，头是$a_{x+y+1}$，因为首拿了$x+y$个，尾是$a_{x+y+1+n-m}$ 因为轮到第$m$个人拿的时候，还有$n-m+1$个数字，那么$z-(x+y+1)+1=n-m+1$，解得$z=x+y+1+n-m$。所以暴力枚举$x$和$y$的值就得到一个$O(n^2)$的算法。最终答案如下
$$b_i=max(a_{1+i}, a_1+i+(n-m))$$
$$ans = max_{x \in [0, k]}\lbrace min_{y \in [0, m-1-k]}b_{x+y} \rbrace$$
# def wrapper(func):
# def inner():
# return next(func)
# return inner
# input = wrapper(open('in.txt'))
T = int(input())
for case in range(T):
n, m, k = map(int, input().strip().split())
a = list(map(int, input().strip().split()))
k = min(m-1, k)
ans = 0
for x in range(k+1):
res = int(2e9)
for y in range(m-k):
res = min(res, max(a[x+y], a[x+y+n-m]))
ans = max(ans, res)
print(ans)
'''
'''令$y’=x+y$，上面的式子可以变化为
$$ans = max_{x \in [0, k]}\lbrace min_{y’ \in [x, x+m-1-k]}b_{y’} \rbrace$$
所以上面的式子可以用线段树来计算，复杂度是$O(nlogn)$，由于求区间最小值的时候区间长度是$m-k$不变的，所以还可以用单调队列来做（和LeetCode的这道题目差不多239. Sliding Window Maximum），复杂度是$O(n)$，下面是单调队列的做法：
# def wrapper(func):
# def inner():
# return next(func)
# return inner
# input = wrapper(open('in.txt'))
import collections
T = int(input())
for case in range(T):
n, m, k = map(int, input().strip().split())
a = list(map(int, input().strip().split()))
k, b = min(m-1, k), []
for i in range(m):
b.append(max(a[i], a[i+n-m]))
ans = 0
d = collections.deque()
for i in range(m):
while d and b[i] <= b[d[-1]]:
d.pop()
while d and (i-d[0]+1 > m-k):
d.popleft()
d.append(i)
if i >= m-k-1:
ans = max(ans, b[d[0]])
print(ans)
'''
'''