CF1397B Power Sequence

我们称一组正整数 $a_0, a_1, \ldots, a_{n-1}$ 为幂序列，如果存在一个正整数 $c$，使得对于每个 $0 \le i \le n-1$，都有 $a_i = c^i$。 给定一组 $n$ 个正整数 $a_0, a_1, \ldots, a_{n-1}$，你可以进行如下操作： - 重新排列该序列（即选择 $\{0,1,\ldots,n-1\}$ 的一个排列 $p$，将 $a_i$ 变为 $a_{p_i}$），然后 - 可以进行任意次数如下操作：选择一个下标 $i$，将 $a_i$ 变为 $a_i-1$ 或 $a_i+1$（即将 $a_i$ 增加或减少 $1$），每次操作的代价为 $1$。 请你求出将 $a_0, a_1, \ldots, a_{n-1}$ 变为一个幂序列的最小代价。

第一行包含一个整数 $n$（$3 \le n \le 10^5$）。 第二行包含 $n$ 个整数 $a_0, a_1, \ldots, a_{n-1}$（$1 \le a_i \le 10^9$）。

输出一个整数，表示将 $a_0, a_1, \ldots, a_{n-1}$ 变为幂序列的最小代价。

在第一个样例中，我们首先将 $\{1, 3, 2\}$ 重新排列为 $\{1, 2, 3\}$，然后将 $a_2$ 增加到 $4$，代价为 $1$，得到幂序列 $\{1, 2, 4\}$。 由 ChatGPT 4.1 翻译