【非零段划分 / 2】

题目


在这里插入图片描述

在这里插入图片描述



思路

第一种思路:按照表面题意,枚举p,处理数组后进行计数: 复杂度 ∈ O ( n ⋅ m ) 复杂度 \in O(n \cdot m) 复杂度O(nm)
第二种思路:把数组看成一个二维的山形图,先将相邻的水平线段转化成点(对数组unique),再对每个子结构进行考虑 复杂度 ∈ O ( m i n ( n , m ) ) 复杂度 \in O(\;min(n, m)\;) 复杂度O(min(n,m))

具体思路:

  1. 先unique,把相邻相等的元素去重
  2. 分为三种子结构,考虑水面暴露其顶点后,其对非零段数量的贡献,记录在cnt[ ]数组中
    2.1. A形结构,只要“水面”暴露出顶点开始,对非零段数量的贡献为+1
    2.2. V形结构,只要“水面”暴露出顶点开始,对非零段数量的贡献为-1 把原本分离的两段合并了
    2.3 / \ 形结构,我们把中间点看作“顶点”,暴露顶点前后贡献不变
  3. 遍历 p f o r [ M − 1 , 1 ] p \; for \;[M-1, 1] pfor[M1,1] 模拟水面降低,维护一个 s u m sum sum 作为计数器


TLE代码


#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int a[N];
int main()
{int n;cin >> n;int amax = 0;for(int i = 1; i <= n; i++) cin >> a[i], amax = max(amax, a[i]);int ans = 0;for(int p = 1; p <= amax; p++){int cnt = 0; int last = 0;for(int i = 1; i <= n; i++){int x = a[i];if(a[i] < p) x = 0;if(x && !last) cnt++;last = x;}ans = max(ans, cnt);}cout << ans;return 0;
}


正确代码


#include <bits/stdc++.h>
using namespace std;
const int N = 5e5+10, M = 1e4+10;
int cnt[M], a[N];
int main()
{int n;cin >> n;for(int i = 1; i <= n; i++) cin >> a[i];n = unique(a+1, a+n+1) - (a+1);a[0] = 0, a[n+1] = 0;for(int i = 1; i <= n; i++){int x = a[i-1], y = a[i], z = a[i+1];if(x < y && z < y) cnt[y]++;if(x > y && z > y) cnt[y]--;}int ans = 0; int sum = 0;for(int i =  M - 1; i >= 1; i--){sum += cnt[i];ans = max(ans, sum);}cout << ans;return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/420002.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

一区霜冰算法+双向深度学习模型+注意力机制!RIME-BiTCN-BiGRU-Attention

一区霜冰算法双向深度学习模型注意力机制&#xff01;RIME-BiTCN-BiGRU-Attention 目录 一区霜冰算法双向深度学习模型注意力机制&#xff01;RIME-BiTCN-BiGRU-Attention效果一览基本介绍程序设计参考资料 效果一览 基本介绍 1.Matlab实现RIME-BiTCN-BiGRU-Attention霜冰算法…

如何本地搭建Whisper语音识别模型

要在本地搭建Whisper语音识别模型&#xff0c;您需要以下几个步骤&#xff1a; 步骤一&#xff1a;系统准备 操作系统: 建议使用Ubuntu 20.04或以上版本&#xff0c;确保系统足够稳定和兼容。硬件配置: 最好有一个强大的GPU&#xff0c;因为语音识别涉及大量的计算工作。推荐…

828华为云征文|华为云Flexus X实例部署k3s与kuboard图形化管理工具

828华为云征文&#xff5c;华为云Flexus X实例部署k3s与kuboard图形化管理工具 华为云最近正在举办828 B2B企业节&#xff0c;Flexus X实例的促销力度非常大&#xff0c;特别适合那些对算力性能有高要求的小伙伴。如果你有自建MySQL、Redis、Nginx等服务的需求&#xff0c;一定…

算法工程师重生之第二天(长度最小的子数组 螺旋矩阵II 区间和 开发商购买土地 总结 )

参考文献 代码随想录 一、长度最小的子数组 给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl1, ..., numsr-1, numsr] &#xff0c;并返回其长度。如果不存在符合条件的子数组&#xff0c…

全网最适合入门的面向对象编程教程:46 Python函数方法与接口-函数与事件驱动框架

全网最适合入门的面向对象编程教程&#xff1a;46 Python 函数方法与接口-函数与事件驱动框架 摘要&#xff1a; 函数是 Python 中的一等公民,是一种可重用的代码块,用于封装特定的逻辑&#xff1b;事件驱动框架是一种编程模式&#xff0c;它将程序的控制流转移给外部事件,如用…

ssm微信小程序校园失物招领论文源码调试讲解

第二章 开发技术与环境配置 以Java语言为开发工具&#xff0c;利用了当前先进的SSM框架&#xff0c;以MyEclipse10为系统开发工具&#xff0c;MySQL为后台数据库&#xff0c;开发的一个微信小程序校园失物招领。 2.1 Java语言简介 Java是由SUN公司推出&#xff0c;该公司于20…

若依框架使用MyBatis-Plus中的baseMapper的方法报错Invalid bound statement (not found):

Invalid bound statement (not found): com.ruoyi.system.mapper.hc.HcOrderMapper.selectList 解决方法 MybatisSqlSessionFactoryBean sessionFactory new MybatisSqlSessionFactoryBean(); 使用 MybatisSqlSessionFactoryBean 而非 SqlSessionFactoryBean 的原因 MyBatis-…

Elasticsearch数据写入过程

1. 写入请求 当一个写入请求&#xff08;如 Index、Update 或 Delete 请求&#xff09;通过REST API发送到Elasticsearch时&#xff0c;通常包含一个文档的内容&#xff0c;以及该文档的索引和ID。 2. 请求路由 协调节点&#xff1a;首先&#xff0c;请求会到达一个协调节点…

1分钟教你用AI制作美女热舞视频,收益可观,操作简单(附工具及教程资料)

美女跳舞&#xff0c;听着是不是就觉得会很哇塞&#xff1f; 不管是男的女的、老的少的都喜欢看&#xff0c;而且一般美女跳舞的账号涨粉都很快&#xff0c;势头都贼猛。 今天就给大家分享一个很热门的小副业——AI美女跳舞。 更多实操和AI绘画工具&#xff0c;可以扫描下方&…

新能源动力组中预充电路及电阻选型分析

新能源动力组中预充电路及电阻选型分析 1.概述2.预充电路与预充电阻3.预充电阻参数选择4.实例分析 1.概述 最近几年&#xff0c;新能源行业在中国得到迅猛发展。由于其高效、节能、低噪声、无污染等特点&#xff0c;它已成为国内工业发展的新趋势包括汽车和飞机。虽然应用在新…

地瓜直播间 | 基于X5平台智能双目深度算法详解

你是否曾经好奇过&#xff0c;机器是如何像人类一样通过双眼来感知三维世界的&#xff1f;双目深度感知技术&#xff0c;是一种模拟人类双眼视觉的高级技术&#xff0c;通过两个摄像头捕捉同一场景的不同视角&#xff0c;深度学习算法能够计算出物体的深度信息&#xff0c;从而…

PX4软/硬件(SITL/HITL)在环仿真

文章目录 介绍依赖PX4 Firmware&#xff1a; 软件在环(SITL)仿真Gazebo 软件无人机STIL连接简要示意SITL SLAM仿真总结示例 HITL 仿真 pxh常用命令MAVLink 指令使用这些命令时的注意事项 参考链接 介绍 为https://blog.csdn.net/weixin_41469272/article/details/117919845的补…

东南亚电商新蓝海:深度解析东南亚服务器租用的战略价值

在全球化日益加深的今天&#xff0c;东南亚以其独特的市场潜力和对数字化技术的积极拥抱&#xff0c;成为了跨境电商及互联网企业竞相角逐的热土。随着东南亚地区经济的快速增长和人口红利的持续释放&#xff0c;电商市场的繁荣景象尤为引人注目。然而&#xff0c;要在这一竞争…

【Linux系统编程】TCP实现--socket

使用套接字socket实现服务器和客户端之间的TCP通信。 流程如下&#xff1a; 实现代码&#xff1a; /* server.c */ #include <stdio.h> #include <stdlib.h> #include <unistd.h> #include <string.h> #include <arpa/inet.h> #include <s…

【C++笔记】类和对象的深入理解(一)

【C笔记】类和对象的深入理解(一) &#x1f525;个人主页&#xff1a;大白的编程日记 &#x1f525;专栏&#xff1a;C笔记 文章目录 【C笔记】类和对象的深入理解(一)前言一.类的定义1.1类定义格式1.2访问限定符1.3类域 二.实例化2.1 实例化概念2.2对象大小 三.this指针四.练…

[A-09]ARMv8/ARMv9-Memory-内存空间(Address Spaces and Translation Regimes)

ver 0.2 更多精彩内容&#xff0c;请关注公众号 前言 任何人和组织的发展都需要空间&#xff0c;比如我们这个伟大的国家&#xff0c;幅员辽阔、大好河山决定了我们的发展潜力。这么大国土空间&#xff0c;不是随意无须的在发展&#xff0c;都是处于主动的规划(有形的手)或者…

【计网】计算机网络基础

当自律变成一种本能的习惯&#xff0c; 你就会享受到它的快乐。 --- 村上春树 --- 初识计算机网络 1 初识协议1.1 协议分层1.2 OSI七层模型1.3 TCP / IP协议 2 初识局域网2.1 什么是局域网2.2 MAC地址2.3 局域网通信 3 简单认识IP地址 1 初识协议 1.1 协议分层 首先&#…

基于微信小程序的人才招聘系统设计与实现

作者&#xff1a;计算机学姐 开发技术&#xff1a;SpringBoot、SSM、Vue、MySQL、JSP、ElementUI等&#xff0c;“文末源码”。 专栏推荐&#xff1a;前后端分离项目源码、SpringBoot项目源码、SSM项目源码 系统展示 基于微信小程序JavaSpringBootVueMySQL的人才招聘系统设计与…

C++ 音频

一、采样频率 当前主流的采样频率为22.05KHz、44.1KHz、48KHz 22.05KHz&#xff1a;为FM广播声音品质 44.1KHz&#xff1a;为理论上最高的CD声音品质&#xff08;直播&#xff0c;录像&#xff0c;acc&#xff09; 48KHz&#xff1a;人耳可分辨的最高采样频率 &#xff08;…

AI预测福彩3D采取888=3策略+和值012路或胆码测试9月9日新模型预测第82弹

经过80多期的测试&#xff0c;当然有很多彩友也一直在观察我每天发的预测结果&#xff0c;得到了一个非常有价值的信息&#xff0c;那就是9码定位的命中率非常高&#xff0c;70多期一共只错了8次&#xff0c;这给喜欢打私房菜的朋友提供了极高价值的预测结果~当然了&#xff0c…