题解：P13091 中位数

· · 题解

思路

显然的，如果可以最终答案为 i，那么对于任意 1\le j\le i，一定存在解使得答案 ans\ge j，故本题答案满足单调性。

考虑二分答案，则需要判断是否可以使答案 ans\ge mid，可以将该问题转化为如下方式解决：

将原数组转化为一个 01 序列，对于 a_i\ge mid 使得 a_i\gets 1，否则对于 a_i< mid 使得 a_i\gets 0，那么原问题变为能否使该序列答案为 1。

相邻数才能合并，所以需要维护一个栈，依次从栈顶加入元素进行处理。

对于连续三个数消去的情况进行分类讨论：

  1. 三个数为 000，删去后变为 0，减少两个 0，故删去一定不劣。
  2. 三个数为 001，010，011，100，101，110 六种情况，可以发现此类情况删去后数列中 1 和 0 减少数量相同，故最后需要比较两者数量多少判断情况可行性，谁多剩下谁。
  3. 三个数为 111，删去少两个 1 一定不优，不删等待后续计算。

根据以上结论 1 将序列中的所有 000 合并，则序列中连续 0 的长度不超过 2。
但是此时直接使用结论 2 比较 0,1 数目是错误的，因为存在诸如 00100 的情况，消去中间的 1 后还会出现 000，直接计算会产生错误。
所以对于 001 的情况也需要直接合并处理，情况 2 其他 5 种则不需要改变，况且后续情况不明，合并不一定优（比如又接上两个 0 什么的都有可能）。

然后根据比较合并后整个序列中 0,1 数目大小即可判断是否存在 ans\ge mid。

还有别忘了多测清空。

代码实现

代码不长，私以为我的码风还是比较朴素正统的，可读性较强，应该方便理解。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int x[100005],y[100005],Q[100005],tail=0,n;
bool check(int u){
    tail=0;
    for(int i=1;i<=n;i++){
        if(x[i]>=u)y[i]=1;
        else y[i]=0;
    }
    for(int i=1;i<=n;i++){
        if(tail>1&&Q[tail]==0&&Q[tail-1]==0)tail--;//001 和 000 的前缀都是 00 就合并处理了
        else Q[++tail]=y[i];
    }
    int summ=0;
    for(int i=1;i<=tail;i++){
        if(Q[i]==1)summ++;
        else summ--;
    }//统计数目遇 0 减一，遇 1 加一，总数为正则 1 比 0 多
    return summ>0;//长度奇数不存在总和为 0
}
signed main(){
    int T;
    scanf("%lld",&T);
    while(T--){
        scanf("%lld",&n);
        for(int i=1;i<=n;i++)scanf("%lld",&x[i]);
        int l=1,r=1e9;
        while(l<r){
            int mid=(l+r+1)/2;
            if(check(mid))l=mid;
            else r=mid-1;
        }
        printf("%lld\n",l);
    }
    return 0;
}