http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1437

1437 迈克步51nod 1437-LMLPHP

题目来源: CodeForces
基准时间限制:1 秒 空间限制:131072 KB 分值: 80 难度:5级算法题
51nod 1437-LMLPHP 收藏
51nod 1437-LMLPHP 关注

有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
和上一题类似,根据元素得出对应区间的最值。
每个元素都对应着在一些区间里是最小值,我们不妨找到以每一个元素为最小值的最大区间,这个大区间所有包含此元素的子区间的力量显然也是这个元素。
 #include <iostream>
#include<algorithm>
#include<stack>
#include<cstdio>
using namespace std;
typedef long long LL;
const int MAX = ;
int a[MAX], l[MAX], r[MAX], f[MAX];
int _() {
int x = , c = getchar();
while (c<)c = getchar();
while (c>)x = x * + c - , c = getchar();
return x;
}
void _(int x) {
static int stk[], stp = ;
if (!x)putchar();
while (x)stk[stp++] = x % , x /= ;
while (stp)putchar(stk[--stp] + );
putchar();
}
int main()
{
int N, i, j, k;
scanf("%d", &N);
for (i = ;i <= N;++i) {
//scanf("%d", a + i);
a[i] = _();
l[i] = r[i] = i;
}
for (i = ,j=N;i <= N;++i,--j) {
while (l[i] != && a[i] <= a[l[i] - ])
l[i] = l[l[i] - ];
while (r[j] != N&&a[j] <= a[r[j] + ])
r[j] = r[r[j] + ];
}
for (i = ;i <= N;++i)
f[r[i] - l[i] + ] = max(f[r[i]-l[i]+],a[i]);
for (i = N - ;i >= ;--i)
f[i] = max(f[i], f[i + ]);
for (i = ;i < N;++i) _(f[i]);//printf("%d ", f[i]);
printf("%d\n", f[N]);
//system("pause");
return ;
}
05-17 16:19