外贸玩具网站,北苑做网站的公司,深入网站开发和运维,国外永久免费云服务器试题编号#xff1a; 202109-2 试题名称#xff1a; 非零段划分 时间限制#xff1a; 1.0s 内存限制#xff1a; 512.0MB
样例1输入
11
3 1 2 0 0 2 0 4 5 0 2样例1输出
5样例1解释 p2时#xff0c;A[3,0,2,0,0,2,0,4,5,0,2]#xff0c;5个非零段依次为[3]、[2]、[2…试题编号 202109-2 试题名称 非零段划分 时间限制 1.0s 内存限制 512.0MB
样例1输入
11
3 1 2 0 0 2 0 4 5 0 2样例1输出
5样例1解释 p2时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解释 p12时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解释 p1时A[1,0,0],此时仅有1个非零段[1]非零段个数达到最大。
样例4输入
3
0 0 0样例4输出
0样例4解释 无论p取何值A都不含有非零段故非零段个数至多为0。 70分代码及思路 思路 1.将所有数据存储到一个数组A中并记录最大值max_A 2.p从1开始遍历到最大值max_A,记录每一次p值下的非零段的个数最大值到数组max1中。 3.判断非零段个数遍历数组找到每一个不为0的值如果该数前一个数为0或者该数是数组的第一个数非零段个数加1。 4.遍历数组max1输出最大值。 分析 该方法属于常规思路比较简单无任何算法优化有很多循环遍历且有双层循环由题目给出的数据范围在双层循环中循环次数有可能达到10^9,显然会超时。
#include iostream
using namespace std;int main()
{int n;int i0,p0,max_A0,max0;cinn;int A[n]{0};for(i0;in;i){cinA[i];if(A[i]max_A) //记录数组A中的最大值 {max_AA[i];}}int max1[max_A]{0}; //开辟数组用来存储每一个p值下的非零段的最大值 for(p1;pmax_A;p) //p从1开始遍历 {for(i0;in;i) //将数组中小于p的数置为0 {if(A[i]p){A[i]0;}}for(i0;in;i) //遍历数组 {if(A[i]!0){//若不为0判断是否是数组的第一个数或者该数的前一个数为0如果是非零段加1 if(i0||A[i-1]0){maxmax1;}}}max1[p]max;max0;}for(i1;imax_A;i) if(max1[i]max){maxmax1[i];}coutmax;return 0;
}提交结果如下 如果要拿到满分那么用常规的思路逻辑肯定不行必须要做一定的优化处理在参考b站视频教程后整理如下 1.读入数组时插入set对数组进行去重和排序方便p值的选取。 2.利用向量vector将set集合中每个元素出现的位置存储在同一个vector向量中。 3.统计初始的非零段个数作为参考值。 与前一种方法有点区别在数组开头和最后加0只需判断当前数不为0并且前一位数为0非零段个数加1即可 4.p依次从set中取值从小到大如果值为0跳过)依据位置向量获得每个值在数组A中的位置。 将对应位置的值赋值为0 如果该位置的前后的值都大于0则非零段数加1; 如果该位置的前后的值都等于0则非零段数减1; 其他情况下非零段个数不变。 更新非零段的最大值。 该方法的优点在于 通过向量对应的位置坐标判断坐标位置前后元素的值进行判断即可不必在每一个p值下都对数组进行循环遍历降低了时间复杂度。 此方法思路来源b站可参考b站视频内容
满分代码
#include bits/stdc.h
using namespace std;int A[500002] {0};
vectorint Vector[10001];
setint Set;int main() {int n;cinn;for(int i1; in; i) {cinA[i];Set.insert(A[i]);Vector[A[i]].push_back(i);}int number0; //非零段个数for(int i1; in; i) { //找出当前非零段的个数if((A[i]0)(A[i-1]0))number;}int temp;int number_max; //非零段个数的最大值tempnumber_maxnumber;setint::iterator pSet.begin();//用迭代器来访问set集合//p的值从集合开始遍历if(*p0) //如果集合中的元素为0则直接从下一个元素开始p;for(p; p!Set.end(); p) {vectorint Vector1Vector[*p]; //引用Vector[*p]为Vector1 for(int i0; iVector1.size(); i) { //集合中该元素出现的总次数int kVector1[i]; A[k]0;if((A[k-1]!0)(A[k1]!0))temp;if((A[k-1]0)(A[k1]0))temp--;}number_maxmax(number_max,temp);}coutnumber_maxendl;return 0;}提交结果如下
