CSP 202109-2 非零段划分 C++ 100

2023-01-05

题目

【题目描述】 A1,A2,···,An是一个由n个自然数（非负整数）组成的数组。我们称其中Ai,···,Aj是一个非零段，当且仅当以下条件同时满足： ·1≤i≤j≤n; ·对于任意的整数k,若i≤k≤j,则$A_k$>0; ·i=1或$A_{i-1}$=0; ·j=n或$A_{j+1}$=0。下面展示了几个简单的例子： ·A=[3,1,2,0,0,2,0,4,5,0,2]中的4个非零段依次为[3,1,2]、[2]、[4,5]和[2]; ·A=[2,3,1,4,5]仅有1个非零段： ·A=[0,0,0]则不含非零段（即非零段个数为0）。现在我们可以对数组A进行如下操作：任选一个正整数p,然后将A中所有小于p的数都变为0。试选取一个合适的P, 使得数组 A 中的非零段个数达到最大。若输入的 A 所含非零段数己达最大值，可取p=1,即不对 A 做任何修改。

【输入格式】从标准输入读入数据。输入的第一行包含一个正整数 n。输入的第二行包含 n 个用空格分隔的自然数A1,A2,···,An。

【输出格式】输出到标准输出。仅输出一个整数，表示对数组 A 进行操作后，其非零段个数能达到的最大值。

【样例输入】

1 2	11 3 1 2 0 0 2 0 4 5 0 2

【样例输出】

代码

#include <bits/stdc++.h>

using namespace std;

const int N=5e5+5;
struct node {
    int x;
    int id;
}a[N];

bool cmp(node A,node B) {
    if(A.x==B.x)
        return A.id<B.id;
    return A.x<B.x;
}

int main()
{
    int n,ans,cnt,pre;
    int b[N]={0};
    cin>>n;
    for(int i=0;i<n;i++)
    {
        a[i].id=i+1;
        cin>>a[i].x;
    }
    sort(a,a+n,cmp);
    b[0]=1;
    b[n+1]=1;
    pre=a[0].x;
    cnt=1;
    ans=0;
    for(int i=0;i<n;i++)
    {
        int id;
        if(a[i].x!=0&&a[i].x!=pre)
            ans=max(ans,cnt);
        id=a[i].id;
        if(b[id-1]==0&&b[id+1]==0)
            cnt++;
        else if(b[id-1]==1&&b[id+1]==1)
            cnt--;
        b[id]=1;
        pre=a[i].x;
    }
    cout<<ans<<endl;
    return 0;
}