专栏文章

题解：P14915 「QFOI R3」算法竞赛

ttuntunQwQ
P14915题解参与者 3已保存评论 3

文章操作

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

当前评论
3 条
当前快照
1 份
快照标识符
@mjsf5370
此快照首次捕获于
2025/12/30 18:02
2 个月前
此快照最后确认于
2025/12/30 18:29
2 个月前
查看原文
数的顺序不影响结果，我们先把数组排序。
对于样例 1，我们依次往队伍中加入 3,3,43,3,4，组成了一支合法的队伍。对于下一个队伍，加入 66 后我们无法加入 99，于是我们依次添加 7,87,8 与 66 构成一组，99 则需要再补两个数和它构成一组，答案就是 44。
对于样例 2，我们依次往队伍中加入 3,3,43,3,4，组成了一支合法的队伍。对于下一个队伍，加入 66 后我们无法加入 99，此时我们添加 88，发现 9−8≤29-8\le 2，则 6,8,96,8,9 构成了一组，答案就是 11。
我们发现，我们想要加入 aia_i 时发现 ai−ai−1>da_i-a_{i-1}>d，则依次在 ai−1a_{i-1} 后面插入 ai−1+d,ai−1+2d,...,ai−1+xda_{i-1}+d,a_{i-1}+2d,...,a_{i-1}+xd，直到能够使 aia_i 加入这个队伍或者把这个队伍填满。
至于为什么每次都要 +d+d，我们的目标是要让加入的数尽可能少，所以我们每次加数要尽可能地减小 aia_i 与新加入数的差，让 aia_i 尽早加入队伍。
记录当前队伍的人数 tottot，若 tot=ktot=k 则新建一个队伍，若发现 ai−ai−1>da_i-a_{i-1}>d 则循环模拟上述过程，否则令 tot=tot+1tot=tot+1。可以得 6060 分，代码：
CPP
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,k,d,a[N],tot,ans;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>k>>d;
	for(int i=1;i<=n;i++)cin>>a[i];
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++){
		if(tot==0)tot++;
		else if(a[i]-a[i-1]<=d){
			tot++;
			if(tot==k)tot=0;
		}
		else{
			int pre=a[i-1];
			while(1){
				pre+=d;
				tot++;
				ans++;
				if(tot==k){
					tot=0;
					break;
				}
				if(a[i]-pre<=d)break;
			}
			if(tot){
				tot++;
				if(tot==k)tot=0;
			}
			else tot++;
		}
	}
	if(tot!=k&&tot)ans+=k-tot;
	cout<<ans;
	return 0;
}
考虑优化：我们其实要找到一个最小的 xx，使得 ai−(ai−1+xd)≤da_i-(a_{i-1}+xd)\le d，整理得 x≥ai−ai−1d−1x\ge \frac{a_i-a_{i-1}}{d}-1，即 x=⌈ai−ai−1d⌉−1x=\lceil \frac{a_i-a_{i-1}}{d}\rceil -1。注意判断当前队伍加上 xx 个数后是否超员，以及 d=0d=0 的情况。
代码如下，可供参考：
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int n,k,d,a[N],tot,ans;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>k>>d;
	for(int i=1;i<=n;i++)cin>>a[i];
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++){
		if(tot==0)tot++;
		else if(a[i]-a[i-1]<=d){
			tot++;
			if(tot==k)tot=0;
		}
		else{
			if(d==0)ans+=k-tot,tot=0;
			else{
				int x=(a[i]-a[i-1]+d-1)/d;
				x--;
				if(tot+x>=k)ans+=k-tot,tot=0;
				else{
					tot+=x;
					ans+=x;
				}	
			}
			tot++;
			if(tot==k)tot=0;
		}
	}
	if(tot!=k&&tot)ans+=k-tot;
	cout<<ans;
	return 0;
}

评论

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

正在加载评论...