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

判断是否可行的代码，然而因为时限只有一秒，理所应当的超时了......

CPP

#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)

。这个复杂度在这道题是绰绰有余的。

这是改进后的代码：

CPP

#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 呢？

文章操作

相关推荐

评论

CF1593D2 题解