Codeforces Round #555 (Div. 3) E. Minimum Array
問題概要
長さ の数列
が与えられます.
の各要素は
以上
以下です.
数列 を,
として定めます.
の各要素を自由に入れ替えて,
が辞書順最小にしてください.
制約
解法
辞書順最小と言われれば, やっぱり貪欲法です. の小さい方から見ていくことにするとき,
に合わせたい数字は何でしょうか？
これは を合わせた時が最もうれしく,
は
になります. この値から
が
増えるごとに,
も
ずつ増えていきます. この嬉しさが毎回最大になるように貪欲に選び続ければいいです.
この貪欲に選び続ける方法は二通りの実装があって, ひとつ目は となる
の数みたいに定義して毎回自分より左で一番小さい要素を二分探索することです. 二周ぶんつくれば実装が多分楽です.
もう一つはセグ木でなんとかすることです. セグ木に みたいな感じでのせて,
が
になったら
を入れます. あとは区間最小値を取ってくるだけです(詳しくは実装を見てください).
実装
多分もっと楽な実装がある
