問題
https://codeforces.com/contest/1538/problem/A
問題文
一列に並んだ 個の石がある。石 の "力" は で、互いに異なる。
毎ターン、左右の端にある石を壊す。
"力" が最大・最小のものを両方とも壊すとき、何ターン必要になる？
制約
サンプル
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;
}