专栏文章

题解：CF985E Pencils and Boxes

___CrossBow_EXE__
CF985E题解参与者 1已保存评论 0

文章操作

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

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

题意

有 nn 支铅笔，每个铅笔有一个权值 aia_i。现在要把所有铅笔放到若干个盒子里，每个盒子至少要放 kk 支铅笔。且一个盒子中任意两只铅笔的权值差的绝对值不能超过 dd。问是否有可行放法。

题解

一眼动态规划。
注意到放的顺序对结果没有影响，考虑先对权值排序。而排序后，我们再把所有铅笔分成若干个区间，每个区间对应放入一个盒子。这样一定是最优的。
定义 dpidp_i 表示前 ii 个铅笔能否全部放入，接着考虑哪一个区间放入了最新的盒子中。假设放入的区间是 [j+1,i][j+1,i]，我们已经枚举了 ii，只要枚举 jj 即可。只要有一个 dpjdp_j 是 11，那 dpidp_i 就是 11。当然，作为初始状态，00 支铅笔肯定能放到 00 个盒子里，所以 dp0=1dp_0=1。
接着，既然我们想要枚举 jj，就要确定枚举的范围 [l,r][l,r]。先求 rr，根据题意，jj 需要满足 k≤i−jk\le i-j 和 ai−aj+1≤da_i-a_{j+1}\le d。第一个不等式稍微变形得 j≤i−kj \le i-k，因此 r=i−kr=i-k。对于 ll 只需要套上第二个式子，找到最后一个满足 ai−al+1≤da_i-a_{l+1}\le d 的 ll 即可。这样代码有两层循环，复杂度为 O(n2)O(n^2)，需要优化。
往回退一步，其实我们只需要判断在 dpldp_l 到 dprdp_r 中有没有 11。如果没有 11，那么 dpl+dpl+1+⋯+dprdp_l+dp_{l+1}+\dots+dp_r 一定为 00；反之，如果这一串的和不为 00，那么这个区间里一定有 11。求区间和，可以用前缀和优化。时间复杂度 O(n)O(n)。

代码

CPP
#include<bits/stdc++.h>
using namespace std;
#define up(_name_,_leftbound_,_rightbound_) for(auto _name_=(_leftbound_);(_name_)<=(_rightbound_);++(_name_))
int n,k,d;
const int N=500005;
int a[N];
int dp[N],sum[N];
int l=0;
bool check(int l,int r){
	if(l>r) return 0;
	else if(!l) return 1;
	else return sum[r]>sum[l-1];
}
signed main(int argc,char *argv[]){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>k>>d;
	up(i,1,n) cin>>a[i];
	sort(a+1,a+n+1);
	dp[0]=sum[0]=1;
	up(i,1,n){
		while(1){
			if(a[i]-a[l+1]<=d) break;
			l++;
		}
		dp[i]=check(l,i-k);
		sum[i]=sum[i-1]+dp[i];
	}
	if(dp[n]) cout<<"YES"<<endl;
	else cout<<"NO"<<endl; 
	return 0;
}
/*
---INFORMATIONS---
TIME:2025/7/6 10:27:27
PROBLEM:CF985E
CODE BY __CrossBow_EXE__ Luogu uid967841
*/

评论

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

正在加载评论...