CF1902C

FiraCode · 2023-12-27 20:52:43 · 题解

思路:

假如没有插入，那么我们发现最后所有的数字都是这个数组的最大值，考虑反证：

设这个数组的最大值为 maxn，假设最后为 maxn+k(k>0) 为最优，那么 maxn 要变成 maxn+k，那么 x \mid k，于是其他的数要先到 maxn 然后再到 maxn+k，所以实际上它相比于变成 maxn 增加了一些操作，所以变成 maxn 比 maxn+k 更优，与假设矛盾。

证毕。

那么一个数组最优的 x 为 \gcd(a_n-a_{n-1},a_{n-1}-a_{n-2},\dots,a_{2}-a_1)。

然后考虑增加一个数字，那么这个数为 maxn+xk，若 k>0 时每次都要 n 的代价，而 k<0 时，只需要找到最大的 k 使得它没有在数组中出现过即可，而代价最多为 n，所以 k<0 一定比 k > 0 更优。

然后就计算每个数到最大值的操作次数再加上插入数字的操作次数即可。

复杂度 O(Tn \log n)。

Code:

#include <bits/stdc++.h>

using namespace std;

#define int long long

int T;
int n;
int a[200010];

int gcd(int a, int b) {
    return !b ? a : gcd(b, a % b);
}

signed main() {
    scanf("%lld", &T);
    while (T--) {
        map<int, int> ma;
        scanf("%lld", &n);
        int Gcd = 0;
        for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]), ma[a[i]] = 1;
        if (n == 1) {
            puts("1");
            continue;
        }
        sort(a + 1, a + 1 + n);
        for (int i = 2; i <= n; ++i) Gcd = gcd(Gcd, a[i] - a[i - 1]);
        int k = -1;
        while (true) {
            if (!ma[a[n] + k * Gcd]) break;
            --k;
        }

        int ans = 0;
        for (int i = 1; i <= n; ++i) ans += (a[n] - a[i]) / Gcd;

        ans -= k;

        printf("%lld\n", ans);
    }
    return 0;
}