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