[Codeforces] Educational Codeforces Round 69 (Div. 2) B. Pillars

2020年9月8日

問題

方針

柱を \( a_1 < a_2 < \cdots < a_n \) のように並び替えることができるかという問題です。どのようにして整列させるかというと、\( a \) を昇順に整列させた配列を \( b \) とします。このとき、\( b_i \) を \( i \) 番目の要素として、\( b_i.id \) を元の配列の添え字とします。一番大きい半径を持つ柱 (\( b_n\)) が一番下になるので、\( b_{n-1} \) を \( b_n \) の上に置くためには、\( |b_n.id – b_{n-1}.id| = 1  \)を満たす必要があります。

柱を上に置いたとき、配列のサイズが一つ減ると考えてよいので、\( b \) に元の配列における、前後の要素の添え字を管理して、配列のサイズが一つ減る操作を実現させます。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct Data {
  int a, idx, prev, next;
  Data(int a, int idx) : a(a), idx(idx){}
  bool operator< (const Data& d) const {
    return a < d.a;
  } 
};

int main() {
  int n;
  cin >> n;
  int a;
  vector<Data> d;
  for (int i = 0; i < n; i++) {
    cin >> a;
    d.push_back(Data(a, i));
    if (i == 0) {
      d[i].prev = -1;
      d[i].next = i + 1;
    } else if (i == n - 1) {
      d[i].prev = i - 1;
      d[i].next = -1;
    } else {
      d[i].prev = i - 1;
      d[i].next = i + 1;
    }
  }
  sort(d.begin(), d.end());
  // for (int i = 0; i < n; i++) {
  //   cout << d[i].a << " " << d[i].idx << "\n";
  // }
  int r = d[n - 1].a;
  for (int i = n - 2; i >= 0; i--) {
    if (d[i].a >= r) {
      cout << "NO\n";
      return 0;
    }
    if (d[n - 1].prev == d[i].idx) {
      d[n - 1].prev = d[i].prev;
    } else if (d[n - 1].next == d[i].idx) {
      d[n - 1].next = d[i].next;
    } else {
      cout << "NO\n";
      return 0;
    }
    r = d[i].a;
  }
  cout << "YES\n";
  return 0;
}