Codeforces Round #618 (Div. 2) - E. Water Balance
概要
長さNの数列Aが与えられる。あなたは次の操作を何度してもよい。
- Aの連続部分列を1つ選び、その連続部分列の亘る区間をすべてその連続部分列の平均とする。
この操作を繰り返して、Aを辞書順に最小にするとき、Aはどうなるか？
制約：1 <= N <= 10^6, 1 <= A_i <= 10^6
入力や出力は多いので、scanf/printfでやる方がいい。
ACするまで
1. 前から見て、整序されてる区間とそうでない区間に分かれて、どんどん整序されてる区間を増やすイメージ。
2. ひとまず、左から、ある場所を始まりとして平均取ったら最小になる右側の場所を求められればよいが、これには「区間を一定の値に変更する」と「区間の最小値を求める」が効率的にできるデータ構造あればいいな！
3. しかしそんなデータ構造なさそう、つらい。コンテスト終了
4. 整序の途中では、「x_iがy_i個続く(ただしx_i
概要
これから{x, y}をxがy個続くと表現する。
この問題でまず考えたのは、貪欲に左から{x_0, y_0}, {x_1, y_1}のような区間があるとき、新たにx_2から始まる区間はどこで終わるか？を考える。この時、次のような機能を持つデータ構造がほしい。
このようなデータ構造を僕は知らないので、ここで考察が詰まっていた。
しかし、考察の常として、考える対象を変える。というのが必要である。今回は、次のようにする。
今見てる値は
- 整序されてる区間の最右端よりも値が大きいのならば、新しく{a[i], 1}として整序されてるブロックに入れる。左のどのブロックと合わせても値を大きくして、辞書順でなくなるからである。
- そうでないのならば、ひとまず整序されてる区間の最右端のブロックと合体する。そして、整序されてる区間の間で、つねに値が広義単調増加になるように、(最右端のブロックの値)>(その1つ前のブロックの値)ならば、その2つのブロックを合わせる。
計算量は、1つの要素に対しては、整序されてる区間内に追加で1回、整序されてる区間内に含まれてる場合、ブロックの合体の操作でたかだか1回なので、全体で線形時間となる。
一言
してやられたなぁ・・・。
以下のブログを参考にした。
www.shangdixinxi.com
谢谢你的详细和说明和代码！
`
