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)
'''

'''