CSP 202109-2 非零段划分

题目链接：非零段划分

题目描述

A1,A2,⋯,An 是一个由 n 个自然数（非负整数）组成的数组。我们称其中 Ai,⋯,Aj 是一个非零段，当且仅当以下条件同时满足：

• 1≤i≤j≤n；
• 对于任意的整数 k，若 i≤k≤j，则 Ak>0；
• i=1 或 Ai−1=0；
• j=n 或 Aj+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输入

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

样例1输出

5

样例1解释

p=2 时，A=[3,0,2,0,0,2,0,4,5,0,2]，5 个非零段依次为 [3]、[2]、[2]、[4,5] 和 [2]；此时非零段个数达到最大。

样例2输入

14
5 1 20 10 10 10 10 15 10 20 1 5 10 15

样例2输出

4

样例2解释

p=12 时，A=[0,0,20,0,0,0,0,15,0,20,0,0,0,15]，4 个非零段依次为 [20]、[15]、[20] 和 [15]；此时非零段个数达到最大。

样例3输入

3
1 0 0

样例3输出

1

样例3解释

p=1 时，A=[1,0,0]，此时仅有 1 个非零段 [1]，非零段个数达到最大。

样例4输入

3
0 0 0

样例4输出

0

样例4解释

无论 p 取何值，A 都不含有非零段，故非零段个数至多为 0。

子任务

70% 的测试数据满足 n≤1000；

全部的测试数据满足 n≤5×10^5，且数组 A 中的每一个数均不超过 10^4。

---

初版无脑暴力代码……有70分诶2333

#include 
#include 
using namespace std;

int main()
{
    int n;
    cin>>n;

    int* a=(int*)malloc(sizeof(int)*n);
    int* b=(int*)malloc(sizeof(int)*n);
    int* c=(int*)malloc(sizeof(int)*n);
    for(int i=0;i>a[i];
        b[i]=a[i];
        c[i]=a[i];
    }
    sort(b,b+n);
    
    int p=0,num=0,max=-1;
    for(int i=0;imax)
        {
            max=num;
        }

        for(int j=0;j 
 把自己能找到的可以优化的地方都改了之后……依然超时，还是70分 
#include 
#include 
#include 
using namespace std;

int main()
{
    int n;
    scanf("%d",&n);

    int* a=(int*)malloc(sizeof(int)*n);
    set b;
    for(int i=0;i::iterator it=b.begin();it!=b.end();it++)
    {
		p=*it;
        if(p==0)
        {
            continue;
        }
        num=0;
        for(int j=0;j=p)
            {
                num++;
                while(a[j]>=p)
                {
                    j++;
                }
                j--;
            }
        }
        if(num>max)
        {
            max=num;
        }
    }
    printf("%d",max);

    return 0;
}
 
没事没事！作为小白还是学到了新知识的！记一下笔记 
对小白很友好的详细介绍： 
(23条消息) STL set 基本介绍_郑丹丹的博客-CSDN博客
 
(23条消息) STL中的set使用方法详细！！！！_知足常乐的博客-CSDN博客
 
关于访问set元素的介绍： 
(23条消息) set容器内元素的访问_Running Snail-CSDN博客_访问set元素
 
(23条消息) STL中的set---可以直接修改set中的元素么？_认知 行动 坚持-CSDN博客
 
//访问set元素
for(set::iterator it=st.begin();it!=st.end();it++)
{
		cout<<*it<<" ";
}
 
最后学习了大佬的解法！ 
(23条消息) csp2021-09-2 非零段划分_隔壁李叟的博客-CSDN博客
 
这个比喻真的好好！一下子就把意思说清楚了√
 
虽然反射弧长的我还是盯着代码看了好久才反应过来是怎么实现的而且下次让我写我可能还是不会
 
笔记笔记 
unique()函数 
#include 
 
这是更具体的介绍：
 
(23条消息) C++中的unique函数_simao-CSDN博客
 
(23条消息) unique()函数详解_大胡子的博客-CSDN博客_unique
 
【整理】C++中的unique函数 - nimphy - 博客园 (cnblogs.com)
 
（小小声，这篇博客的界面好好看喔，打开之后和右下角的小人玩了好久才想起来看讲解XD