C - Make It Good

問題

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

問題文

長さ $n$ の数列 $a$ の先頭からいくつかの要素を削除して、 いい配列 にしたい。
削除する必要がある要素の最小値は？

数列 $b$ が いい配列 であるとは、$b$ が空になるまで以下の操作を繰り返して、最初は空の配列 $c$ を広義単調増加にできることをいう。

$b$ の先頭か末尾のどちらかから要素を選ぶ。
選んだ要素を $b$ から削除し、 $c$ の末尾に加える。

制約

• $1 \le t \le 2 \times 10^4$
• $1 \le n \le 2 \times 10^5$
• $1 \le a_i \le 2 \times 10^5$
• $n$ の総和は $2 \times 10^5$ を超えない

サンプル

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

0
4
0
2
3

考察

決め打ち二分探索 + 貪欲法した。解説は全然そんなことしてなかった

具体的には、 $k$ を決め打ちして、 $a$ の先頭 $k$ 個を削除してから、貪欲に いい配列 にできるか判定する。
先頭/末尾の要素のうち、小さいほうから順番に $c$ に加えていくのが最適。

コード

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

bool chk(deque<int> dq, int start) {
  int prev = 0;
  if (start >= dq.size()) return false;
  while (start--) dq.pop_front();
  while (!dq.empty()) {
    int fr = dq.front();
    int ba = dq.back();
    if (fr >= prev && fr <= ba) {
      prev = fr;
      dq.pop_front();
    }
    else if (ba >= prev && ba <= fr) {
      prev = ba;
      dq.pop_back();
    }
    else if (fr >= prev) {
      prev = fr;
      dq.pop_front();
    }
    else if (ba >= prev) {
      prev = ba;
      dq.pop_back();
    }
    else {
      break;
    }
  }
  return dq.empty();
}

void solve() {
  int n;
  cin >> n;
  deque<int> dq;
  rep(i, n) {
    int a;
    cin >> a;
    dq.push_back(a);
  }
  int ok = n - 1, ng = -1;
  while (abs(ok - ng) > 1) {
    int mid = (ok + ng) / 2;
    if (chk(dq, mid)) {
      ok = mid;
    }
    else {
      ng = mid;
    }
  }
  cout << ok << endl;
}