题解 AT4894 【[ABC136C] Build Stairs】

· · 题解

ChungZH's blog · ChungZH's portfolio

从左到右连续排列 N 个正方形。从左起第 i 个正方形的高度为 H_i。

对于每个正方形，您将一次执行以下任一操作：

  • 将正方形的高度减少 1。
  • 什么都不做

确定是否可以执行操作，以使正方形的高度从左到右不减小。

输入完之后，从后往前推，如果 h_{i-1} 和 h_i 的差大于 1，说明怎么操作也不可以了，输出 No。

如果 h_{i-1}-1==h_i，说明还可以抢救一下通过操作变成一样多，也就是不减小，把 h_{i-1}-1 之后继续推下去。

#include <algorithm>
#include <cctype>
#include <cstdio>
#include <iostream>
using namespace std;
int n;
long long h[100005];
int main() {
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> h[i];
  }

  for (int i = n - 1; i > 0; i--) {
    if (h[i - 1] - 1 > h[i]) {
      cout << "No\n";
      return 0;
    } else if (h[i-1]-1 == h[i]) {
      h[i-1]--;
    }
  }

  cout << "Yes\n";
  return 0;
}