CFR 794 E. Choosing Carrot ( Game, Ad hoc )

Problem - 794E - Codeforces

題意：
給長度 N 的數列 A[]。現在輪流玩遊戲，選擇一個端點的元素，讓它消失。當元素數量為 1 的時候遊戲立即結束。先手的目標是最大化最後一個元素，後手的目標是最小化最後一個元素。先手打算作弊，自己操作連續 K 輪後，當作那是一個新局開始進行遊戲。問對於所有 0 ≤ K < N，最後一個元素會是多少。

制約：
N ≤ 3e5
1 ≤ A[ i ] ≤ 1e9

解法：
考慮 K = 0：
__若 n 是 1：自明
__若 n 是奇數，那麼答案是 min( A[ n + 1 >> 1 ], max( A[ n - 1 >> 1 ], A[ n + 3 >> 1 ] ) )
__若 n 是偶數，那麼答案是 max( A[ n >> 1 ], A[ n + 2 >> 1 ] )
至於 K > 0，利用單調性，以及類似擴散更新 ( 初始時只能取中間那塊，隨著 K 越大，就可以往左右擴散 ) 的方式得到答案。

複雜度：
O( N )

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

const int MAXN = int( 3e5 );

int N;
int _A[ MAXN + 2 ], *A = &_A[ 1 ];

int ans[ MAXN ];

signed main() {
  ios::sync_with_stdio( 0 );
  cin >> N;
  for( int i = 0; i < N; ++i ) {
    cin >> A[ i ];
  }
  for( int i = N - ( N & 1 ), best = 0, lp = N / 2 - 1, rp = ( N + 1 ) / 2; i >= 1; i -= 2, --lp, ++rp ) { // how many left
    best = max( { best, max( A[ lp ], A[ lp + 1 ] ), max( A[ rp - 1 ], A[ rp ] ) } );
    ans[ N - i ] = best;
  }
  for( int i = N - ( ~N & 1 ), best = 0, lp = ( N - 1 ) / 2, rp = N / 2; i >= 1; i -= 2, --lp, ++rp ) {
    best = max( { best, min( A[ lp ], max( A[ lp - 1 ], A[ lp + 1 ] ) ),
                        min( A[ rp ], max( A[ rp - 1 ], A[ rp + 1 ] ) ) } );
    ans[ N - i ] = best;
  }
  for( int i = 0; i < N; ++i ) {
    ans[ N - 1 ] = max( ans[ N - 1 ], A[ i ] );
  }
  for( int i = 0; i < N; ++i ) {
    cout << ans[ i ] << " \n"[ i + 1 == N ];
  }
  return 0;
}