2019牛客暑期多校训练营(第一场) - A - Equivalent Prefixes - 单调栈
2024-09-06 00:54:29
A - Equivalent Prefixes - 单调栈
题意:给定两个n个元素的数组a,b,它们的前p个元素构成的数组是“等价”的,求p的最大值。“等价”的意思是在其任意一个子区间内的最小值相同。
考虑使用单调栈去弄它。每次单调栈中的元素会回答以栈顶元素为结尾的区间的最小值是多少。
比如数组:
2,4,3,5,1
前1个元素的单调栈:
{{2,1}}
意思是[1,1]的最小值是2
前2个元素的单调栈:
{{2,1},{4,2}}
意思是[1,2]的最小值是2,[2,2]的最小值是4
前3个元素的单调栈:
{{2,1},{3,3}}
意思是[1,3]的最小值是2,[2,3]的最小值是3,[3,3]的最小值是3
前4个元素的单调栈:
{{2,1},{3,3},{5,4}}
意思是[1,4]的最小值是2,[2,4]的最小值是3,[3,4]的最小值是3,[4,4]的最小值是5
前5个元素的单调栈:
{{5,1}}
意思是[x,5]的最小值都是1
所以每次只需要比较单调栈的大小就可以知道是不是新加的元素可以使得数组保持“等价”。
要是使用单调队列,那么在新元素入队之前弹空,弹出的时候可以顺便把一系列的区间最值给刷新掉。
#include<bits/stdc++.h>
using namespace std;
int a[500005];
int b[500005];
stack<int> sta, stb;
int main() {
int n;
while(~scanf("%d", &n)) {
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
for(int i = 1; i <= n; i++) {
scanf("%d", &b[i]);
}
int ans = 0;
for(int i = 1; i <= n; i++) {
while(!sta.empty() && sta.top() >= a[i])
sta.pop();
sta.push(a[i]);
while(!stb.empty() && stb.top() >= b[i])
stb.pop();
stb.push(b[i]);
if(sta.size() != stb.size())
break;
else
ans++;
}
printf("%d\n", ans);
while(!sta.empty())
sta.pop();
while(!stb.empty())
stb.pop();
}
}
不用STL会更省内存,但不一定会更快。其实这个算法是在线的,a和b可以不存。
#include<bits/stdc++.h>
using namespace std;
int a[500005];
int b[500005];
int sta[500005], statop;
int stb[500005], stbtop;
int main() {
int n;
while(~scanf("%d", &n)) {
for(int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for(int i = 1; i <= n; i++)
scanf("%d", &b[i]);
int ans = 0;
statop = 0, stbtop = 0;
for(int i = 1; i <= n; i++) {
while(statop && sta[statop] >= a[i])
statop--;
sta[++statop] = a[i];
while(stbtop && stb[stbtop] >= b[i])
stbtop--;
stb[++stbtop] = b[i];
if(statop != stbtop)
break;
else
ans++;
}
printf("%d\n", ans);
}
}
最新文章
- JavaScript单线程和浏览器事件循环简述
- 为html.EditorFor添加样式
- Caffe学习系列(10):命令行解析
- 轻量级的jquery
- C++注意事项锦集
- poj3349 哈希
- 跨站点端口攻击 – XSPA(SSPA)
- http://www.cnblogs.com/leiOOlei/p/5075402.html
- HTTP返回码总结
- Windows环境变量设置无效解决办法——DOS窗口设置环境变量
- firebug加载不了js脚本文件问题
- PCA, SVD以及代码示例
- bootstrap简单图文环绕效果
- Java基础语法<;四>; 控制流程
- 关于InnoDB的读写锁类型以及加锁方式
- Python3之max key参数学习记录
- 第 16 章 C 预处理器和 C 库(预定义宏)
- SharePoint 2013 APP 开发示例 (四)JQuery访问REST
- [Linux] 硬盘构造与分区
- 数据分析常用的python工具和SQL语句
热门文章
- Airbnb JavaScript 编码风格指南(2018年最新版)
- nodejs http服务器简单搭建
- 关于windows服务器配置
- BZOJ3129/洛谷P3301方程(SDOI2013)容斥原理+扩展Lucas定理
- rabbit-c编译 vs2013
- 51nod 1028 大数乘法 V2 【FFT模板题】
- 调整ceph的pg数(pg_num, pgp_num)
- python 全栈开发,Day53(jQuery的介绍,jQuery的选择器,jQuery动画效果)
- 【HDOJ6614】AND Minimum Spanning Tree(签到)
- Apache检查配置文件语法