Codeforces_Round_616_(Div_2)_C题

• 2020 年 2 月 18 日
• 筆記

题目大意

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