题解：CF2222C Median Partition

MaxBlazeResFire · 2026-04-28 09:56:50 · 题解

来点赛时不卡的技巧。

枚举中位数 x 是自然的。令 >x 为 1，\leq x 为 -1 生成数组 b，<x 为 1，\geq x 为 1 生成数组 c，每一段都必须满足 b,c 区间和不大于 0。

然而你只会 O(n^3)。

这个题正解不可能是对顶堆，贪心你试过是假的，那就只能是 dp。只能平方怎么办？于是我们猜只有全局中位数有用。

确实是对的。非全局中位数生成的 b,c 数组为 1 的部分至少有一个严格大于一半，不可能分成若干不大于 0 的区间和。

::::success[Code]

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

#define int long long
#define MAXN 200005

int n,m,a[MAXN],dp[MAXN],tt[MAXN];
int b[MAXN],c[MAXN];

inline int check( int x ){
    //< x: -1,>x : 1，和
    for( int i = 1 ; i <= n ; i ++ ){
        if( a[i] < x ) b[i] = -1; else b[i] = 1;
        if( a[i] > x ) c[i] = 1; else c[i] = -1;
        b[i] += b[i - 1],c[i] += c[i - 1],tt[i] = tt[i - 1] + ( a[i] == x );
    }
    dp[0] = 0;
    // cerr << x << "\n";
    for( int r = 1 ; r <= n ; r ++ ){
        dp[r] = -(int)1e9;
        for( int l = 0 ; l < r ; l ++ ){
            if( ( r - l ) % 2 == 0 ) continue;
            if( b[r] - b[l] >= 0 && c[r] - c[l] <= 0 && tt[r] - tt[l] > 0 )
                dp[r] = max( dp[r] , dp[l] + 1 );
        }
    }
    // cerr << b[3] << " " << c[3] << "\n";
    return dp[n];
}

inline void solve(){
    scanf("%lld",&n);
    map<int,int> M;
    for( int i = 1 ; i <= n ; i ++ ) scanf("%lld",&a[i]),M[a[i]] ++;
    int s = 0,mid = 0;
    for( pair<int,int> ele : M ){
        s += ele.second;
        if( s >= ( n + 1 ) / 2 ){
            mid = ele.first;
            break;
        }
    }
    // cerr << mid << "\n";
    int ans = check( mid );
    printf("%lld\n",ans);
}

signed main(){
    int t; scanf("%lld",&t);
    while( t -- ) solve();
    return 0;
}

::::