51nod 1153 选择子序列(单调队列)
发布日期:2021-11-02 09:48:32 浏览次数:1 分类:技术文章

本文共 1149 字,大约阅读时间需要 3 分钟。

题目

长度为N的整数数组A,所有的数均不相同,假设下标从0开始。找到一个最长的数组B,B数组的长度为K,数值范围是0 - N - 1,记录的是A数组的下标。满足A[B[0]] > A[B[1]] > A[B[2]] >…A[B[K]],并且对任意连续的两项B[i]及B[i + 1],满足min(B[i],B[i + 1]) < j < max(B[i],B[i + 1]) 均有A[j] < A[B[i + 1]] ,求最大的K。例如:9, 10, 2, -1, 3, -5, 0, -3, 1, 12, 5, 8, -2, 6, 4。可以选出:12, 10, 3, 1, 0, -3。对应的下标为:9, 1, 4, 8, 6, 7(就是B数组),输出6。

输入

第1行:一个数N,表示A数组的长度。(1 <= N <= 50000)

第2 - N + 1行:每行1个数对应A数组的元素Ai(0 < Ai < 109)

输出

输出B数组最长的长度K。

输入样例

15

9
10
2
-1
3
-5
0
-3
1
12
5
8
-2
6
4

#include 
#include
#include
#include
using namespace std;struct node {
int val, num; node(int v, int n) {
val = v; num = n; }};int main() {
int n; cin >> n; stack
buf; int a, result = 0; for (int i = 0; i < n; i++) {
cin >> a; int num = 0; while (!buf.empty() && a > buf.top().val) {
num = max(num, buf.top().num); buf.pop(); } num++; int size = buf.size() + 1; num = max(num, size); buf.push(node(a, num)); result = max(result, num); } cout << result << endl; return 0;}

转载地址:https://blog.csdn.net/weixin_43820352/article/details/108186007 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:51nod 1128 正整数分组 V2(二分数组)
下一篇:Java 设计模式(目录)

发表评论

最新留言

感谢大佬
[***.8.128.20]2024年03月26日 06时43分36秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

php云盘匿名,PHP7之匿名类 2019-04-21
matlab数据大小不兼容,MATLAB无法执行赋值,因为左侧的索引与右侧的大小不兼容。 求解... 2019-04-21
editor.md使用php,editor.md 配置参数和使用方法 2019-04-21
python mod,mod_python的安装 2019-04-21
python分析彩票数据,这波太炸了!Python脚本可视化居然可以这么玩 2019-04-21
简单的mysql重置root密码,重置mysql的root密码最简单的方法 2019-04-21
用matlab仿真mmc环流抑制器,一种基于准PR控制原理的MMC阀组环流抑制方法 2019-04-21
oracle 排序的分析函数,Oracle SQL:使用分析排序函数 2019-04-21
oracle direct for hdfs xi下载,ORACLE连接HDFS有个专项的解决方案 2019-04-21
java 403怎么抛出_java – 如何在Spring MVC中返回403禁止? 2019-04-21
java jsch工具类_Java工具集-JSch连接远程服务器工具类 2019-04-21
cmd背景变红1003无标题_怎样修改cmd中文字的大小、颜色和背景颜色呢 原来是这样的... 2019-04-21
php rand() 重复,php – mt_rand()给我总是相同的数字 2019-04-21
php taglib.php,thinkphp5 taglib自定义标签教程 2019-04-21
java常用包类 array,Java中的StringBuffer和数组Arrays以及常用类型的包装类 2019-04-21
ctf常见php,CTF中常见的PHP伪协议 2019-04-21
php语言冒泡法,PHP 冒泡排序法 2019-04-21
php如何数组去重复,PHP如何去除数组重复元素? 2019-04-21
java转换ab的值,查看新闻/公告--[整理]Java将AB1234形式的16进制字符串转换为10进制数值,考虑字节序的影响.... 2019-04-21
ui php h5,画出自己的UI组件的详情 2019-04-21