非常好玩的一道博弈論的題目，結(jié)論與證明都非常巧妙，在翻月賽題目時(shí)看到的。蒟蒻希望能盡可能地講清楚思考過程和結(jié)論的證明，如有問題請(qǐng)指出。

原題鏈接。

題目分析

為方便敘述，我們稱分割的人為先手，另外一個(gè)人為后手。

二分答案 \(x\)，將原序列中大于等于 \(x\) 的位置變?yōu)?\(1\)，反之變?yōu)?\(0\)。那么問題就轉(zhuǎn)化為雪能否取到 \(1\)。

我們記新序列中 \(1\) 的個(gè)數(shù)為 \(cnt_1\)，\(0\) 的個(gè)數(shù)為 \(cnt_0\)。我們猜測，當(dāng) \(cnt_1 > cnt_0\) 時(shí)，雪一定能贏；當(dāng) \(cnt_1 < cnt_0\) 時(shí)，K 一定能贏。

證明：問題的關(guān)鍵就是證明某一方的優(yōu)勢(shì)能否一直保持。

1. 當(dāng) \(cnt_1 > cnt_0\) 時(shí)，被 K 分割后回有兩種情況：兩段都是 \(cnt_1' > cnt_0'\)；一段是 \(cnt_1' > cnt_0'\)，一段是 \(cnt_1' = cnt_0'\)。我們只需考慮第二種情況。

   \(cnt_1' = cnt_0'\) 的這一段非常特別，我們只考慮它在右邊的情況。記 \(pre_{i,1}, pre_{i,0}\) 分別表示 \(1,0\) 個(gè)數(shù)的前綴和，這個(gè)序列只有最后一個(gè)位置滿足 \(pre_{i, 1} = pre_{i, 0}\)，否則我們可以將前面這些 \(pre_{i, 1} = pre_{i, 0}\) 的小段合并到做左邊的序列，這樣也符合我們的設(shè)定。

   這么說可能有點(diǎn)抽象，下面舉個(gè)例子。比如 1 1 0 1 0 1 0 這個(gè)序列，如果我們選擇從 \(3\) 位置分開，即分成 1 1 0 和 1 0 1 0。但是我們完全可以把第一段 1 0 合并到左邊，即分成 1 1 0 1 0 和 1 0。

   如果這個(gè)序列只有最后一個(gè)位置滿足 \(pre_{i, 1} = pre_{i, 0}\)，那么 K 在任何一個(gè)位置分，都會(huì)分成 \(cnt_1' > cnt_0'\) 和 \(cnt_1' < cnt_0'\) 的兩段，雪完全可以選擇 \(cnt_1' > cnt_0'\) 的這一段，那么雪的優(yōu)勢(shì)便能一直保持。

2. 當(dāng) \(cnt_1 < cnt_0\) 時(shí)，證明與 \(cnt_1 > cnt_0\) 的方法一樣，不多贅述。

我們?cè)賮硐胂?\(cnt_1 = cnt_0\) 時(shí)的情況，咱先來手模幾個(gè)。1 0 1 0 雪能贏，1 0 1 0 1 0 K能贏，1 0 1 0 1 0 1 0 雪又能贏。我們發(fā)現(xiàn)每個(gè)人的輸贏好像是交替出現(xiàn)的。

我們把滿足 \(pre_{i, 1} = pre_{i, 0}\) 的 \(i\) 稱為一個(gè)“前綴點(diǎn)”。觀察上面的例子，猜測如果有奇數(shù)個(gè)前綴點(diǎn)，那么 K (后手)能贏；如果有偶數(shù)個(gè)前綴點(diǎn)，雪(先手)能贏。

首先要發(fā)現(xiàn)的一點(diǎn)是，雪和 K 都不可能在前綴點(diǎn)以外的位置分割，與上文一樣，這樣一定會(huì)分成 \(cnt_1' > cnt_0'\) 和 \(cnt_1' < cnt_0'\) 的兩段，那么下一個(gè)人就可以根據(jù)自己的需求選擇一段，從而獲取勝利。

我們可以用歸納證明：設(shè)前綴點(diǎn)個(gè)數(shù)為 \(m\)。

1. \(m\) 為奇數(shù)：當(dāng) \(k = 1\) 時(shí)，根據(jù)情況1的結(jié)論，后手能贏。假設(shè)當(dāng) \(k = m\) 時(shí)成立，當(dāng) \(k = m + 2\) 時(shí)，前兩輪先手都在倒數(shù)第二個(gè)前綴點(diǎn)分開 (這一定不會(huì)使答案變壞，可以仔細(xì)想想)，那么剩下的就是 \(k = m\) 的情況，注意此時(shí)的先手沒變，情況完全相同。

2. \(m\) 為偶數(shù)：同樣地，選擇倒數(shù)第二個(gè)前綴點(diǎn)分開，情況變成了 \(n\) 為奇數(shù)時(shí)的情形，不過現(xiàn)在的后手是剛開始的先手，那么先手一定能贏。

所以我們只需要找到最大的滿足 \(cnt_1 > cnt_0\) 的數(shù)即可，這在原序列中就是中位數(shù)。不過注意，當(dāng) \(n\) 為偶數(shù)時(shí)，還要判斷 \(\frac{n}{2} + 1\) 位置上的數(shù)是否可行。

如果排序求中位數(shù)，時(shí)間復(fù)雜度為 \(O(n \log n)\)，如果是線性求，則可做到 \(O(n)\)。

Code

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

constexpr int N = 1e5 + 9;
int n;
int a[N], b[N], pre[2];

void solve(){
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i], b[i] = a[i];
    sort(b + 1, b + 1 + n);
    if(n & 1){
        cout << b[(n + 1) / 2] << '\n';//中位數(shù)
        return;
    }
    int x = b[n / 2 + 1];//偶數(shù)要特判
    int res = 0;
    for(int i = 1; i <= n; i++){
        int c = (a[i] >= x);
        pre[c]++;
        if(pre[0] == pre[1]) res++;
    }
    if(res & 1) cout << b[n / 2] << '\n';
    else cout << x << '\n';

    pre[1] = pre[0] = 0;
}

int main(){
    int T;
    cin >> T;
    while(T--) solve();
    return 0;
}