题目描述

此处

思路

进阶指南P55

代码

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

struct node{
    int v,id;
}a[200005];

bool cmp(node x,node y){
    return (x.v<y.v||x.v==y.v&&x.id<y.id);
}

int n,mxt[200005],mit[200005],ans;
bool tag;
int main(){
    cin>>n;
    for (int i=1;i<=n;++i) scanf("%d",&a[i].v),a[i].id=i;
    sort(a+1,a+n+1,cmp);
    int last=1e8;
    for(int i=1;i<=n;i++){
        if (a[i].v!=a[i-1].v || i==1) mit[i]=a[i].id;
        else mit[i]=mit[i-1];
    }
    for (int i=n;i>=1;--i){
        if (a[i].v!=a[i+1].v || i==n) mxt[i]=a[i].id;
        else mxt[i]=mxt[i+1];
    }
    for (int i=1;i<=n;++i){
        if (a[i].v==a[i-1].v&&i!=1) continue;
        if (!tag){
            if (last<mit[i]) last=mxt[i];
            else tag^=1,last=mit[i],ans++;
        }else{
            if (mxt[i]<last) last=mit[i];
            else tag^=1,last=mxt[i];
        }
    }
    printf("%d\n",ans);
    return 0;
}

拓展

还有一提类似的题目，见进阶指南P54

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/73/