CF Round #725 A - Stone Game


Tags:cpcodeforcesdiv3greedyexhaustive_search

問題

https://codeforces.com/contest/1538/problem/A

問題文

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

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

制約

  • 1t1001 \le t \le 100
  • 2n1002 \le n \le 100
  • 1ain1 \le a_i \le n

サンプル

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;
}