| 试题编号： | 202109-2 |
| 试题名称： | 非零段划分 |
| 时间限制： | 1.0s |
| 内存限制： | 512.0MB |
| 问题描述： | 题目描述 A1,A2,⋯,An 是一个由 n 个自然数（非负整数）组成的数组。 我们称其中 Ai,⋯,Aj 是一个非零段，当且仅当以下条件同时满足：
下面展示了几个简单的例子：
现在我们可以对数组 A 进行如下 *** 作：任选一个正整数 p，然后将 A 中所有小于 p 的数都变为 0。 试选取一个合适的 p，使得数组 A 中的非零段个数达到最大。 若输入的 A 所含非零段数已达最大值，可取 p=1，即不对 A 做任何修改。 从标准输入读入数据。 输入的第一行包含一个正整数 n。 输入的第二行包含 n 个用空格分隔的自然数 A1,A2,⋯,An。 输出到标准输出。 仅输出一个整数，表示对数组 A 进行 *** 作后，其非零段个数能达到的最大值。 p=2 时，A=[3,0,2,0,0,2,0,4,5,0,2]，5 个非零段依次为 [3]、[2]、[2]、[4,5] 和 [2]；此时非零段个数达到最大。 p=12 时，A=[0,0,20,0,0,0,0,15,0,20,0,0,0,15]，4 个非零段依次为 [20]、[15]、[20] 和 [15]；此时非零段个数达到最大。 p=1 时，A=[1,0,0]，此时仅有 1 个非零段 [1]，非零段个数达到最大。 无论 p 取何值，A 都不含有非零段，故非零段个数至多为 0。 70% 的测试数据满足 n≤1000； 全部的测试数据满足 n≤5×10^5，且数组 A 中的每一个数均不超过 10^4。 |
看其他人写的题解的时候，看到了有人用海岛来解释这个问题，觉得很有意思，在这我也试试，嘿嘿。
p可以理解为海平面
数组的每个元素可以理解为图上的黑点
当海平面足够高时，所有的岛屿都被淹没(也就是当p足够大时，A数组里所有元素都变为0，没有非零段)
当海平面下降时，有的岛屿浮出水面，出现凸峰(p减小到一定程度时，A中有的元素不为0，也就出现了非零段)
当海平面继续下降，我们发现出现凹谷把两个岛屿连接成了一个(A中两个非零段连起来了)
不难得出，出现一个凸峰，非零段加1，出现一个凹谷，非零段减1。
从A数组的最大值到A数组的最小值，每一个p对应了不同的非零段个数，仔细思考发现每次p的改变都会导致在上一次非零段个数上的基础上加上或减去新出现的凸峰数或凹谷数，并且露出水面的数必然是比之前的露出水面的数要小(这点先注意一下)。
因此我们可以用一个数组储存A数组每个数的状态(以凸峰出水就是1，以凹谷出水就是-1，在水下就是0)。
最后求数组后缀和(看前面注意的点，d[n-1]+=d[n],所以求得是后缀和)，得到一个新的数组，新数组的最大值就是最大非零段个数。
#include
#include
#include
using namespace std;
int main()
{
int n,a[500001],d[10010],p,q;
cin>>n;
for(int i=0;i>a[i];
memset(d,0,sizeof(d));//一开始全部在水下
p=*max_element(a,a+n);
q=*min_element(a,a+n);//记录a数组的最大最小值，减少下面循环次数
int j=unique(a,a+n)-a-1;//删去重复的相邻元素，这有说法的
for(int i=1;ia[i-1]&&a[i]>a[i+1])
d[a[i]]++;//凸峰
if(a[i]a[1])
d[a[0]]++;
if(a[j]>a[j-1])
d[a[j]]++;//对于边界，不会有凹谷的情况，但是会有凸峰
for(int i=p;i>=q-1;i--)
d[i-1]+=d[i];
p=*max_element(d+1,d+p+1);//求最大值
cout< 下面对代码里几个值得注意的点解释一下：
去重这里不是把4个10，变成1个10，而是把重复的元素用后面的代替：
即：把1图的结构化为2图的结构，符合求解该题的思想
边界处理
左图边界视为凸峰，非零段加1，右图边界啥都不是，不做 *** 作。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）