涉及知识点:鸽巢原理,贪心
前言
唐诗题,赛时都已经想到了所有性质,以为要从数学方法上求解,却没想到就是个纯贪心题……
题意
给你一堆数,\(1,2,3,\dots,n\),分别有 \(a[1],a[2],a[3],\dots,a[n]\) 个,你还可以添加不超过 \(k\) 个数(当然这些数得是 \(1\sim n\) 中的整数),你需要将它们划分成若干组,使得组内数的总数相同,且组内不存在相同的数,求组中数的个数的最大值。\(2\leq n \leq 2\times 10^5\),\(0\leq k \leq 10^{16}\),\(0\leq a[i]\leq 10^{10}\)。
思路
我们记一组中数的个数为 \(s\),共有 \(d\) 组,根据题意显然 \(s\cdot d=\sum{a[i]}+k\)。
- \(s\leq n\)。由于一组中的数要求不重复,而数的可能的取值只有 \(n\) 种,根据鸽巢原理,一组的大小 \(s\) 不可能大于 \(n\)。
- \(d\geq \max\{a[i]\}\)。由于一组种的数要求不重复,根据鸽巢原理,如果对于某个 \(i\),\(d\leq a[i]\),那么至少存在一组,组中有多于 \(1\) 个的 \(i\),因此 \(d\) 不可能小于任意 \(a[i]\)。
因此我们考虑从大到小枚举所有可能的 \(s\),判断其是否可行,也就是找到是否存在 \(d\) 满足 \(s\cdot d=\sum{a[i]}+k'\),并且 \(0\leq k'\leq k\),那么我们去找满足 \(s\cdot d\geq \sum{a[i]}\) 的最小的 \(d\) 即可,因为如果最小的那个 \(d\) 都不满足 \(k'\leq k\),那么更大的 \(d\) 也一定不会满足。
反思
在做这道题的时候一直想的是如何用数学方法同时最优化 \(s\) 和 \(d\) 这两个数,但是实际上 \(s\) 是可枚举的,而且判断一个 \(s\) 是否可行也不用一一尝试所有 \(d\),赛时脑子没转过弯。
代码
int n;
LL k,a[MAXN],sum,maxx;
inline void solve(){
sum=0;maxx=0;
rd(n);rd(k);
for(int i=1;i<=n;i++){
rd(a[i]);
sum+=a[i];
maxx=max(maxx,a[i]);
}
for(LL s=n;s>=1;s--){
if(maxx*s>=sum && k>=maxx*s-sum){
wt(s,'\n');
return;
}
else if(maxx*s<sum){
LL delta=sum-maxx*s;
delta=(ceil((double)delta/(double)s))*s;
if(k>=maxx*s+delta-sum){
wt(s,'\n');
return;
}
}
}
wt(1,'\n');
}
标签:10,maxx,一组,cdot,sum,Partition,leq,CF2019C,Cards
From: https://www.cnblogs.com/SkyNet-PKN/p/18438458