当前位置: 首页 > news >正文

外贸玩具网站北苑做网站的公司

外贸玩具网站,北苑做网站的公司,深入网站开发和运维,国外永久免费云服务器试题编号#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;}提交结果如下
http://www.pierceye.com/news/146921/

相关文章:

  • vip影视网站如何做appwordpress centos查看目录
  • 网站怎么套模板山西seo博客
  • 好看的手机网站推荐新建的网站 找不到
  • 网站站内搜索怎么做seo搜索优化
  • 建设部网站 测绘规章pc网站手机网站
  • 建网站如何赚钱vs哪个版本做网站好
  • 新衡阳网站游戏软件开发公司简介
  • 湖南基础建设投资集团网站做体育最好的网站
  • 上海php网站开发公司wordpress 邮件认证
  • 教做香肠的网站张家港专业网站建设
  • 园林建设网站营销型网站的建站步骤是什么意思
  • 招聘求职网站html模板正规的创业商机网
  • 预付网站建设费会计处理哪里建网站好
  • 做免费网站艺术学院网站建设管理办法
  • 做网站贵吗手机网站wap
  • linux建立网站做网站的应该怎么发广告
  • wordpress使用端口百度seo排名软
  • 用英文字母做网站关键词个人网站的设计与实现专业论文图像处理工具
  • 重庆企业网站推广流程php网站开发技术训练心得
  • 汽车销售网站学校建网站
  • 两台电脑一台做服务器 网站潍坊专业网站建设多少钱
  • 青岛科技街网站建设安徽 网站开发
  • 黑糖不苦建设的网站wordpress获取文章图片不显示
  • 美食网站建设的功能免费做简历的网站
  • 网站建设公司谁管手机如何创建网站
  • 可以自己做网站优化吗最好用的wordpress主题
  • 瓜子二手车网站开发智慧团建注册登记入口
  • 青岛网站开发建设安阳市商祺网络有限责任公司
  • 自己怎么做装修网站网站建设设计岗位职责
  • php语言 网站建设投资2 3万小生意