非官方题解|挑战赛#21-T3

T3午枫的分割数组

• 难度：普及-

• 思路分析

1. 准备部分
   从左到右扫描数组，计算每个位置的前子表最大值lm[]及其出现次数lc[]
   从右到左扫描数组，计算每个位置的后子表··最大值rm[]及其出现次数rc[]
2. 枚举所有可能的分割方案
   对于每个可能的分割点 $m（2 ≤ m ≤ n）$
   将数组分为两部分：前 $m-1$ 个元素给小午，后 $n-m+1$ 个元素给小枫
   根据预处理结果：
   小午部分的最大值为 $lm_{m-1}$，可选数量为min(lc[m-1],k1)
   小枫部分的最大值为 $rm_m$，可选数量为min(rc[m],k2)
3. 胜负判断
   对于每个分割方案：
   比较小午部分最大值 $wm$ 和小枫部分最大值 $fm$
   只要找到一个分割方案满足 $wm > fm$ ，则立即返回YES，若检查完所有分割方案都没有找到满足条件的，则返回NO

• 通过代码

#include<bits/stdc++.h>
using namespace std;
int a[1000010];
int lm[1000010],lc[1000010];
int rm[1000010],rc[1000010];
 
int main(){
    int n,k1,k2;
    cin>>n>>k1>>k2;
    for(int i=1;i<=n;i++)cin>>a[i];
 
    //计算前子表最大值及出现次数 
    lm[1]=a[1];
    lc[1]=1;
    for(int i=2;i<=n;i++){
        if(a[i]>lm[i-1]){
            lm[i]=a[i];//更新最大值
            lc[i]=1;
        }
        else if(a[i]==lm[i-1]){//等于当前最大值 
            lm[i]=a[i];
            lc[i]=lc[i-1]+1;//计数
        }
        else{//小于当前最大值 
            lm[i]=lm[i-1];
            lc[i]=lc[i-1];
        }
    }
 
    //计算后子表最大值及出现次数 
    rm[n]=a[n];
    rc[n]=1;
    for(int i=n-1;i>=1;i--){
        if(a[i]>rm[i+1]){//当前元素大于之后最大值
            rm[i]=a[i];
            rc[i]=1;
        }
        else if(a[i]==rm[i+1]){//等于当前最大值 
            rm[i]=a[i];
            rc[i]=rc[i+1]+1;
        }
        else{//小于当前最大值
            rm[i]=rm[i+1];
            rc[i]=rc[i+1];
        }
    }
 
    //枚举所有可能的分割点 
    for(int m=2;m<=n;m++){
        int wm=lm[m-1];//小午部分的最大值 
        int wt=min(lc[m-1],k1);//小午可选该最大值的数量 
        int fm=rm[m];//小枫部分的最大值 
        int ft=min(rc[m],k2);//小枫可选该最大值的数量 
 
        if(wm>fm){//判断是否小午必胜 
            cout<<"YES";
            return 0;
        }
    }
    cout<<"NO";
}

• 时间复杂度 $O(n)$，