题解：CF985E Pencils and Boxes

· · 题解

题意

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

题解

一眼动态规划。

注意到放的顺序对结果没有影响，考虑先对权值排序。而排序后，我们再把所有铅笔分成若干个区间，每个区间对应放入一个盒子。这样一定是最优的。

定义 dp_i 表示前 i 个铅笔能否全部放入，接着考虑哪一个区间放入了最新的盒子中。假设放入的区间是 [j+1,i]，我们已经枚举了 i，只要枚举 j 即可。只要有一个 dp_j 是 1，那 dp_i 就是 1。当然，作为初始状态，0 支铅笔肯定能放到 0 个盒子里，所以 dp_0=1。

接着，既然我们想要枚举 j，就要确定枚举的范围 [l,r]。先求 r，根据题意，j 需要满足 k\le i-j 和 a_i-a_{j+1}\le d。第一个不等式稍微变形得 j \le i-k，因此 r=i-k。对于 l 只需要套上第二个式子，找到最后一个满足 a_i-a_{l+1}\le d 的 l 即可。这样代码有两层循环，复杂度为 O(n^2)，需要优化。

往回退一步，其实我们只需要判断在 dp_l 到 dp_r 中有没有 1。如果没有 1，那么 dp_l+dp_{l+1}+\dots+dp_r 一定为 0；反之，如果这一串的和不为 0，那么这个区间里一定有 1。求区间和，可以用前缀和优化。时间复杂度 O(n)。

代码

#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
*/