51nod 1437 迈克步——单调栈
2024-09-06 03:46:37
有n只熊。他们站成一排队伍，从左到右依次1到n编号。第i只熊的高度是ai。
一组熊指的队伍中连续的一个子段。组的大小就是熊的数目。而组的力量就是这一组熊中最小的高度。
迈克想知道对于所有的组大小为x（1 ≤ x ≤ n）的，最大力量是多少。
Input
单组测试数据。
第一行有一个整数n (1 ≤ n ≤ 2×10^5)，表示熊的数目。
第二行包含n个整数以空格分开，a1, a2, ..., an (1 ≤ ai ≤ 10^9),表示熊的高度。
Output
在一行中输出n个整数，对于x从1到n，输出组大小为x的最大力量。
Input示例
10
1 2 3 4 5 4 3 2 1 6
Output示例
6 4 4 3 3 2 2 1 1 1 求出以每个元素为最小值的区间的左边界和右边界，保存下来，r[i] - l[i] +1 就是a[i]可作为最小值的区间的最大长度，然后这个长度的区间肯定包含这个长度-1的区间，于是依次取最大值。
#include<stdio.h>
#include<cstring>
#include<iostream>
#include<algorithm>
#define MAXSIZE 200005 using namespace std; int a[MAXSIZE],l[MAXSIZE],r[MAXSIZE],s[MAXSIZE],ans[MAXSIZE]; int main()
{
freopen("in.txt","r",stdin);
memset(ans,,sizeof(ans));
memset(s,,sizeof(s));
int n,top;
cin>>n;
for(int i=;i<=n;i++)
cin>>a[i];
top = ;
for(int i=;i<=n;i++)
{
if(top==)
{
s[++top] = i;
l[i] = i;
} else
{
while(top>= && a[s[top]]>=a[i])
{
top--;
}
if(top==)
l[i] = ;
else
l[i] = s[top]+;
s[++top] = i;
}
} top = ;
for(int i=n;i>=;i--)
{
if(top==)
{
s[++top] = i;
r[i] = i;
} else
{
while(top>= && a[s[top]]>=a[i])
{
top--;
}
if(top==)
r[i] = n;
else
r[i] = s[top]-;
s[++top] = i;
}
} for(int i=;i<=n;i++)
{
ans[r[i]-l[i]+] = max(ans[r[i]-l[i]+],a[i]);
}
for(int i=n-;i>=;i--)
{
ans[i] = max(ans[i+],ans[i]);
}
for(int i=;i<=n;i++)
{
if(i!=) cout<<" ";
cout<<ans[i];
}
return ;
}
最新文章
- RSA3：预提取数据
- mseed2sac的安装和使用
- 程序员下一门要学的编程语言Swift
- java 12-3 StringBuffer的添加和删除功能
- [转载] C++11中的右值引用
- 转载-使用 Feed4JUnit 进行数据与代码分离的 Java 单元测试
- IconRes提供免费高质量的Material风格android官方图标库
- 理解js闭包（一）
- qt widget设置Qt::FramelessWindowHint和Qt::WA_TranslucentBackground, 会出现一个bug: 在最小化后还原时界面停止刷新
- 以a为变量名，给出下列描述的定义
- C# 多线程 方法，类的标记
- xcode 4 制作静态库详解
- Opengl坐标转换
- Java连接mysql——Establishing SSL connection without server's identity verification is not recommended.
- 安装Oracle Grid的过程中用到的几个小技巧
- 字符转ASCII码
- 工具SQL
- Eclipse配置Maven的一些问题
- Java入门：一些初学者需要掌握的基础算法程序——二分查找
- Charles连接苹果及JSON乱码情况解决