CF1593D2 题解

· · 题解

题目传送门

蒟蒻做的第二十八道 CF 题！让我们看看题意：

有一个包含 n 个数的整数序列 a，你需要找到一个最大的数 k，使得进行若干次 a_i \rightarrow a_i - k 操作后 a 数组有至少一半的数相等，其中 1 \le \sum n \le 100,-10^6 \le a_i \le 10^6。

拿到题目后，发现 n 总和只有 100，能不能试试暴力水过？

首先判断 k 可以为任意数的情况：将 k 定为一个极大数，若还能满足条件，说明 k 肯定取值是没有上界了，可以输出 -1。

我们也可以探索：当 k 有最大值时，这个值的上界是什么呢？

首先因为不能随意取值，所以这个 k 至少会让两个整数变成相同值，否则就不可能满足 a 数组有至少一半数相等这条限制了。

所以说，存在两个数 x 和 y 使得 x 可以通过操作变成 y。那么就可以发现，x - y 的上界，也就是 2 \times 10^6，也是 k 的上界。

所以我就交了一发将 k 从 2 \times 10^6 + 1 一直枚举到 1 判断是否可行的代码，然而因为时限只有一秒，理所应当的超时了......

#include <iostream>
using namespace std;
int t,n,a[105],b[2000005];//a_i是数组，b_i是桶
int main()
{
    cin >> t;
    while(t --)
    {
        cin >> n;
        for(int i = 1;i <= n;i ++)cin >> a[i];
        int maxx = 0;
        for(int i = 2000001;i >= 1;i --)
        {
            for(int j = 1;j <= n;j ++)
            {
                int k = (a[j] % i + i) % i;//注意负数取模后是负数，一定得将它变成正数
                b[k] ++;//如果两个数可以变成相同，那么它们在模k意义下必须同余
                if(b[k] >= n - n / 2)
                {
                    maxx = i;
                    break ;
                }
            }
            for(int j = 1;j <= n;j ++)b[(a[j] % i + i) % i] = 0;
            if(maxx)break ;
        }
        if(maxx > 2e6)cout << "-1\n";
        else cout << maxx << '\n';
    }
}

看来我们枚举的个数还是太多。让我们优化一下上面的代码：因为存在两个整数 x 和 y 使得 x 可以通过若干次操作变成 y，那么 x - y 一定是 k 的倍数（很容易证明，因为 x 要正好减到 y）。那么我们就可以通过枚举 x - y 的所有因数，将这些因数收集起来再检查就可以通过这题啦！

因为一组数据的 n 只到 40，所以只需要枚举 n^2 个数的因子，而一个数的因数个数是 \log n 级别的，所以容易证明出复杂度是 \mathcal{O}(n^3 \log a_i)。这个复杂度在这道题是绰绰有余的。

这是改进后的代码：

#include <iostream>
#include <algorithm>
using namespace std;
int t,n,a[105],b[2000005],c[200005],cnt = 0;//c数组存储可能的k值
int main()
{
    cin >> t;
    while(t --)
    {
        cin >> n,cnt = 0;
        for(int i = 1;i <= n;i ++)cin >> a[i];
        for(int i = 1;i <= n;i ++)
            for(int j = i + 1;j <= n;j ++)
            {
                int k = abs(a[i] - a[j]);
                for(int l = 1;l * l <= k;l ++)
                    if(k % l == 0)c[++cnt] = l,c[++cnt] = k / l;
            }
        sort(c + 1,c + cnt + 1);
        int cnt2 = unique(c + 1,c + cnt + 1) - c - 1,maxx = 0;//为保证复杂度，记得去重
        c[++cnt2] = 2000001;
        for(int i = cnt2;i >= 1;i --)
        {
            for(int j = 1;j <= n;j ++)
            {
                int k = (a[j] % c[i] + c[i]) % c[i];
                b[k] ++;
                if(b[k] >= n - n / 2)
                {
                    maxx = c[i];
                    break ;
                }
            }
            for(int j = 1;j <= n;j ++)b[(a[j] % c[i] + c[i]) % c[i]] = 0;
            if(maxx)break ;
        }
        if(maxx > 2e6)cout << "-1\n";
        else cout << maxx << '\n';
    }
}

这里也包含了 CF1591D1 的代码，将 n - n / 2 改成 n 即可。话说这道题值不值 *1900 呢？