hdu6215 Brute Force Sorting（模拟）
2024-09-07 10:02:39
题意
给一个长度为n(n<=1e5)的序列，如果一个位置i满足a[i-1]>a[i]或者a[i]>a[i+1]，那么我们就称该位置是不合法的位置
先把序列中所有不合法的位置统一找出来，然后再一起删除，剩下的合并成一个新序列
再对新序列重复操作，直至最后每个位置都是合法的
现在你需要输出最后的序列长什么样
分析
如果根据题意用链表去直接暴力模拟那么会T
会T的原因就是可能有很多不应该被删除的位置我们去从前往后遍历了很多遍
注意发现一个规律，某一次可能的不合法位置一定是上一次不合法位置的左边或者右边
所以我们可以利用并查集维护每个元素当前的左边和右边，然后每次将上一次删除的位置记录下来，这一次只需要check那些位置的左边或者右边是否合法就行了
时间复杂度O(n)
最新文章
- HashMap两种遍历方式的深入研究
- Qt——透明无边框Widget的bug
- Hololens开发笔记之Gesture手势识别（Manipulation手势控制物体旋转）
- crm 2013邮箱设置 “允许使用凭据进行电子邮件处理” 被禁用的解决
- 第2章 数字之魅——斐波那契（Fibonacci）数列
- thymeleaf 内联语法
- javascript 的基本优化
- sql server中的索引详情
- jQuery动画高级用法（上）——详解animation中的.queue()动画队列插队函数
- ZOJ 2859 二维RMQ（模板）
- Oracle创建物化视图
- 第四次oo博客
- 腾讯云服务器突然远程连不上（包含ssh，拒绝访问）
- sublime将python的运行结果在命令行显示
- numpy 从入门到遗忘
- EHR ORA--1187由于验主频雘失败而无法从文件读取 ORA-01110数据文件temp01.dbf
- .NET平台开源文档与报表处理组件包括Execel PDF Word等
- Android 控件： Webview 的一些知识点
- 第三百七十一节，Python分布式爬虫打造搜索引擎Scrapy精讲—elasticsearch(搜索引擎)用Django实现我的搜索以及热门搜索
- oracle之 11.2.0.4 bbed安装