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

2020年9月4日2020年12月13日

問題

方針

配列 \( 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)}\]

の範囲で調べます。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n;
ll a[100000]{};
ll best = 0;

void solve(ll c) {
    ll v = a[0] - 1;
    ll m = c;
    for (int i = 1; i < n; i++) {
        v += abs(a[i] - m);
        m *= c;
        if (v > best) {
            return;
        }
    }
    best = v;
}


int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a, a + n);
    for (int i = 0; i < n; i++) {
        best += a[i] - 1;
    }
    ll v = best + a[n - 1];
    ll ub = pow(v, (double) 1 / (n - 1)) + 1;
    for (ll c = 2; c <= ub; c++) {
        solve(c);
    }
    cout << best << "\n";
    return 0;
}