A - Stone Game

cpcodeforcesdiv3greedyexhaustive search

最終更新日

Table of Contents

Loading...

問題

https://codeforces.com/contest/1538/problem/A (新しいタブで開く)

問題文

一列に並んだ nn 個の石がある。石 ii の "力" は aia_i で、互いに異なる。
毎ターン、左右の端にある石を壊す。

"力" が最大・最小のものを両方とも壊すとき、何ターン必要になる?

制約

サンプル

5 5 1 5 4 3 2 8 2 1 3 4 5 6 8 7 8 4 2 3 1 8 6 7 5 4 3 4 2 1 4 2 3 1 4
2 4 5 3 2

考察

最小・最大を取るまでの途中で左右を変えるのは無意味。

制約が小さいので、全パターン調べる。
具体的には、左から/右から始めて、最小・最大を取るまでのターン数を調べる。
取り終わったら、内側にある最大・最小を、また左右で調べる。

コード

https://codeforces.com/contest/1538/submission/125443650 (新しいタブで開く)

ll sol(deque<ll> dq, ll maxim, ll minim, bool fromL, bool contL) { ll ans = 0; bool got = false; while (!dq.empty()) { ll now = (fromL ? dq.front() : dq.back()); ans++; (fromL ? dq.pop_front() : dq.pop_back()); if (now == maxim || now == minim) { break; } } while (!dq.empty()) { ll now = (contL ? dq.front() : dq.back()); ans++; (contL ? dq.pop_front() : dq.pop_back()); if (now == maxim || now == minim) { break; } } return ans; } void solve() { int n; cin >> n; deque<ll> dq; ll minim = 1e3, maxim = -1; rep(i, n) { ll a; cin >> a; dq.push_back(a); minim = min(minim, a); maxim = max(maxim, a); } ll ans = sol(dq, maxim, minim, false, false); // R->R ans = min(ans, sol(dq, maxim, minim, false, true)); // R->L ans = min(ans, sol(dq, maxim, minim, true, false)); // L->R ans = min(ans, sol(dq, maxim, minim, true, true)); // L->L cout << ans << endl; return; }