[Codeforces] Codeforces Round #666 (Div. 2) B. Power Sequence

2020年9月8日

問題

方針

配列 \( a \) を昇順に並び替えて考えます。自然数 \( x \) を選んだ時のコストを \( f(x) \) とすると、

\[ f(x) = \sum_{i=0}^{n-1} |x^i-a_i|\]

となります。ここで、\( x = (f(1) + a_{n-1})^{-(n-1)} \) とすると、

\[ f((f(1) + a_{n-1})^{-(n-1)})  \geq f(1) \]

となるので、

\[ 1 \leq x \leq (f(1) + a_{n-1})^{-(n-1)}\]

の範囲で調べます。

コード