Minimize Max Diff
<問題>
csacademy.com
長さの非減少数列が与えられる。
このうち個までの要素を削除することができ、削除後に隣り合う要素の差の最大値を最小にしたい。
そのときの最小値はいくらか。
<解法>
可能な値を2分探索します。
ここでが取りうる値かどうかは、
元の数列のうち、隣り合う要素の差が全て以下の連続する部分列の最大長をとすると、
となっているかどうかで判定できます。
単純に、個取り除いた後に、条件を満たす数列が存在することを確かめればよいです。
<コード>
int n, k; vi a; bool ok(int mid) { int ml = 0; rep(i, n) { int tl = 0; while ( i + tl+1 < n && a[i + tl+1] - a[i + tl] <= mid ) tl++; ml = max(ml, tl+1); i += tl; } if (ml >= n - k)return true; else return false; } int main() { cin >> n >> k; a.resize(n); rep(i, n)cin >> a[i]; int l = -1, r = 1e9 + 10; while (l + 1 < r) { int mid = (l + r) / 2; if (ok(mid))r = mid; else l = mid; } P(r); return 0; }
<感想>
実は、K個削除する際、左から個 右から個削除することが最適であるとわかります。
(解説にも書いてある通り、数列の真ん中を削除しても、隣り合う数列の差は大きくなるだけです)
これをすべてのについて試せばおkなのですが、途中で出てくる候補の管理ができずに1時間半くらい溶かしてしまいました・・・。
その後ググって2分探索解法にたどり着きました。