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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
感谢大佬
[***.8.128.20]2024年03月26日 06时43分36秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
php云盘匿名,PHP7之匿名类
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
java 403怎么抛出_java – 如何在Spring MVC中返回403禁止?
2019-04-21
java jsch工具类_Java工具集-JSch连接远程服务器工具类
2019-04-21
php rand() 重复,php – mt_rand()给我总是相同的数字
2019-04-21
php taglib.php,thinkphp5 taglib自定义标签教程
2019-04-21
ctf常见php,CTF中常见的PHP伪协议
2019-04-21
php语言冒泡法,PHP 冒泡排序法
2019-04-21
php如何数组去重复,PHP如何去除数组重复元素?
2019-04-21
ui php h5,画出自己的UI组件的详情
2019-04-21