专栏文章

CF484B

DDDF_
CF484B题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miomps7n
此快照首次捕获于
2025/12/02 21:43
3 个月前
此快照最后确认于
2025/12/02 21:43
3 个月前
查看原文

题面

一个数组，求数组中大数模小数的最大值。

题解

你好。重复的元素没有用，而且由于只需要满足 ai≥aja_{i} \ge a_{j}，所以可以直接排序并去重。
第一个暴力就是直接从小到大排序并去重，然后枚举 i∈[1,n],j∈[1,i)i \in [1,n],j \in [1,i)，时间复杂度 O(n2)O(n^{2})。
然后发现这里的 aia_{i} 有一些特殊的数据性质，它只开到了 10610^{6}，于是可以打出第二个暴力。
排序去重后，枚举 aia_{i}，并从大到小枚举它的模数 jj 判断 jj 是不是可行的解，我开了个桶存 sis_{i} 表示 ii 在不在数组 aa 中，然后由 x=j+aix=j+a_{i} 往上跳，如果遇到 sx=1s_{x}=1，则此时 jj 唯一个合法的解。
然后发现不管怎么剪枝复杂度还是过不了，那考虑再次优化算法。
把枚举 jj 优化，对于每个 aia_{i}，由 x=2×aix=2 \times a_{i} 向上跳。找在 [x−ai,x)[x-a_{i},x) 中离 xx 最近的数字。
还记得 ai≤106a_{i} \le 10^{6} 吗？开一个数组 ss， sxs_{x} 存最大的 aia_{i} 使得 ai≤xa_{i} \le x（[1,x][1,x] 中离 xx 最近的数）。所以对于每个 aia_{i} 有 sai=ais_{a_{i}}=a_{i}，接着做一下前缀处理就行了。
最后只需要求 sx−1s_{x-1}，并且判断一下它是否在区间 [x−ai,x)[x-a_{i},x) 中即可。
令 mm 为 aia_{i} 的最大值，排序去重后往上跳的时间开销为 T(∑i=1nmai)T(\sum_{i=1}^{n} \frac {m}{a_{i}})，不超过调和级数 O(mlog⁡m)O(m \log m)。

代码

CPP
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+15;
int n;
int a[N],s[N*10],m;
int ans;
int main() {
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]),m=max(a[i],m);
	sort(a+1,a+1+n);
	n=unique(a+1,a+1+n)-a-1;
	for(int i=1;i<=n;i++) s[a[i]]=a[i];
	for(int i=1;i<=2*m;i++) if(!s[i]) s[i]=s[i-1];
	for(int i=1;i<n;i++) {
		for(int j=2*a[i];j<=m+a[i];j+=a[i]) {
			if(s[j-1]>j-a[i]) ans=max(ans,s[j-1]%a[i]);
		}
	}
	printf("%d",ans);
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...