https://www.acmicpc.net/problem/13323
https://www.acmicpc.net/problem/13324
[BalticOI 2004] Sequence 数字序列 - 洛谷
長さ $N$ の整数列 $A=(A_1,A_2,\dots,A_N)$ が与えられる。
狭義単調増加整数列である $B$ であって、 $\displaystyle \sum_{i=1}^{N} |A_i-B_i|$ が最小となるものを求めよ。
$1 \le N \le 10^6$
考えやすいように、 $A_i = A_i-i$ と見做して議論する。このもとで、 $B$ は広義単調増加整数列という制約に変化する。
初手からわからなかったのでヒントを頂く。
题解-BOI 2004 Sequence - oier_hzy - 博客园 に中央値というワードがあったので、それをもとに考察開始。
確かに、全体をひとつの値で揃えるべき状況であれば中央値に揃えるべきである。
しかし、このとき例えば $(5,5,5,5,8)$ みたいな状況で全体を $5$ 揃えてしまうとロスが出る。
このもとで、どこまでが中央値以下でどこからが中央値以上か… みたいな問題を考察しにかかる。
しかし、なんとこの時点で「中央値」という要素を捨てないとこの先の解法が頓挫してしまう。自分はこの後も「中央値」に拘り過ぎて迷走した。
本当に考察するべき問題は、「どこまでが $x$ 未満」「どこからどこまでがちょうど $x$ 」「どこからが $x$ 超過」の判定問題。
「どこまでが $x$ 未満」という判定問題を考察するにあたって、 $L < R$ なるふたつの整数に対して、接頭辞 $(A_1,A_2,\dots,A_L)$ と $(A_1,A_2,\dots,A_R)$ とを比較する。
区間 $S = (A_{L+1},A_{L+2},\dots,A_R)$ に含まれる $x$ 未満の要素の個数を $C_{<}$ 、 $x$ 以上の要素の個数を $C_{\ge}$ とする。
- $C_{<} < C_{\ge}$ であれば、 $S$ を「 $x$ 未満」に割り当てていたのを「ちょうど $x$ に割り当てることで解が改善する。」
- $C_{<} = C_{\ge}$ であっても、 $S$ を「ちょうど $x$ 」に割り当てるに比べて 「 $x$ 未満」が改善することはない。
- $C_{<} > C_{\ge}$ であれば、 $S$ を「ちょうど $x$ 」に割り当てていたのを「 $x$ 未満」に割り当てることで解が改善する(例えば、全部 $x-1$ にすればよい)。
よって、 $x$ 未満の要素を $+1$ 点、 $x$ 以上の要素を $-1$ 点として最高得点を叩き出す接頭辞のうち最も短いものを「 $x$ 未満」に割り当てることが最適である。
「 $x$ 以上」についても同様。また、「 $x$ 未満」の接頭辞と「 $x$ 以上」の接尾辞が交わることもない。
あとはこれを再帰的にやることで、 $O(N \log A_i)$ でこの問題に正解できる。
luogu の形式に従ったACコード: https://ideone.com/SYavXR
slope trick 使っても行けるらしい。考えもしなかったな…
行けました めんどいので復元抜き https://ideone.com/KfZU6X
