[Codeforces] Educational Codeforces Round 69 (Div. 2) B. Pillars
問題
方針
柱を \( 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; }
ディスカッション
コメント一覧
まだ、コメントがありません