Codeforces 574D Bear and Blocks

题目链接

https://codeforces.com/contest/574/problem/D

题目大意

给你一个长度为 N 的序列，其中 ai 表示 i 这个位置有 ai 的木块

现在进行游戏，每轮可消除木块（若某木块的上或左或右没有木块则可以消除）

问要消除所有木块最多要几轮

解题思路

思维

首先转换题意 , 把消除所有木块转换成要将所有列的木块个数变为 0

这样就可以按列考虑考虑

那么要消除一列，我们需要的最少步骤会是多少呢?

很显然要消除的条件有三种：

①、前一列为空，那么下一轮这列必然可以被消灭

②、后一列为空，那么下一轮这列必然可以被消灭

③、每轮该列至少消灭最上方的木块，那么经过 ai 轮后该列就能被删除

我们记录 L[i] 为从左往右逐列消灭的最优解，R[i] 为从右往左逐列消灭的最优解

于是 L[i] = min(L[i - 1] + 1 , a[i]) , R[i] = min(R[i + 1] + 1 , a[i])

ans = max(ans , min(L[i] , R[i]))

AC_Coder

#include<bits/stdc++.h>
#define rep(i , a , n) for(int i = a ; i <= n ; i ++)
#define per(i , n , a) for(int i = n ; i >= a ; i --)
using namespace std;
const int N = 2e5 + 10;
int a[N] , l[N] , r[N] , n , ans;
signed main()
{
    cin >> n;
    rep(i , 1 , n) cin >> a[i] , l[i] = min(l[i - 1] + 1 , a[i]);
    per(i , n , 1) r[i] = min(a[i] , r[i + 1] + 1) , ans = max(ans , min(l[i] , r[i]));
    cout << ans << '
';  
    return 0;
}