「51nod 1519」拆方块

发表于

有 nn 堆方块，第 ii 堆方块由 hih_i 个方块堆积而成。

接下来拆方块。一个方块称为内部方块当且仅当他的上下左右都是方块或者是地面。否则方块就是边界方块。每一次操作都要把边界方块拿掉。

问多少次操作之后所有方块会消失。

avatar

Constraints

1≤n≤1051 \leq n \leq 10^5

Solution

观察可得，每一轮进行的操作为 hi=min(hi−1,hi−1,hi+1)h_i=min(h_{i-1},h_i-1,h_{i+1}) 。当一列方块被拆掉时，下一轮他的相邻两列中未被拆掉的列也会被拆掉。

从左往右和从右往左分别扫一遍，取 min 即是当前列被拆掉的操作次序。时间复杂度 O(n)O(n) 。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<cstdio>
#include<algorithm> 
#include<cstring>
#define LL long long
using namespace std;
const int N=1e5+5;
int n,ans,h[N],l[N],r[N];
int read()
{
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
}
int main()
{
	n=read();
	for(int i=1;i<=n;i++)h[i]=read();
	l[1]=1;for(int i=2;i<=n;i++)l[i]=min(l[i-1]+1,h[i]);
	r[n]=1;for(int i=n-1;i>=1;i--)r[i]=min(r[i+1]+1,h[i]);
	for(int i=1;i<=n;i++)ans=max(ans,min(l[i],r[i]));
	printf("%d",ans);
	return 0;
}