描述
题解
十分有趣的题,我们从左往右遍历一遍,每个 a[i] 要么是比 a[i−1] 多一次操作,要么是 h[i] 次,取小的;接着从右往左同理搞一遍,获取了 b[] ,初始化 a[0]=b[n−1]=1 。最后呢,从这 a[i]、b[i] 中取小,再在这 n <script type="math/tex" id="MathJax-Element-367">n</script> 个数中取最大即可。
很好玩,仔细观察不难发现这个规律。有些贪心意味……
代码
#include <iostream>
#include <cstdio>
using namespace std;
const int MAXN = 1e5 + 5;
int n;
int h[MAXN];
int a[MAXN];
int b[MAXN];
template <class T>
inline void scan_d(T &ret)
{
char c;
ret = 0;
while ((c = getchar()) < '0' || c > '9');
while (c >= '0' && c <= '9')
{
ret = ret * 10 + (c - '0'), c = getchar();
}
}
int main()
{
while (cin >> n)
{
for (int i = 0; i < n; i++)
{
scan_d(h[i]);
}
a[0] = b[n - 1] = 1;
for (int i = 1; i < n; i++)
{
a[i] = min(a[i - 1] + 1, h[i]);
}
for (int i = n - 2; i >= 0; i--)
{
b[i] = min(b[i + 1] + 1, h[i]);
}
int res = 0;
for (int i = 0; i < n; i++)
{
res = max(res, min(a[i], b[i]));
}
printf("%d\n", res);
}
return 0;
}