欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Codeforces - Pencils and Boxes

程序员文章站 2023-12-25 22:24:27
...

题目链接:Codeforces - Pencils and Boxes


显然可以dp,dp[i] 为前 i 个是否合法。

然后sort一下,然后枚举当前位置的时候,二分或者尺取找到最远的合法的位置。然后就找到了转移区间,只要转移区间有一个合法的,那么当前也是合法的。


AC代码:

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=5e5+10;
int n,k,d,a[N],dp[N],sum[N];
inline int ask(int l,int r){return sum[r]-sum[l-1];}
signed main(){
	cin>>n>>k>>d;
	for(int i=1;i<=n;i++)	scanf("%d",&a[i]);
	sort(a+1,a+1+n);
	for(int i=k;i<=n;i++){
		sum[i]=sum[i-1];
		if(a[i]-a[i-k+1]>d)	continue;
		int l=1,r=i-k+1;
		while(l<r){
			int mid=l+r>>1;
			if(a[i]-a[mid]<=d)	r=mid;
			else l=mid+1;
		}
		if(l==1||ask(l-1,i-k))	dp[i]=1;
		sum[i]+=dp[i];
	}
	puts(dp[n]?"YES":"NO");
	return 0;
}

上一篇:

下一篇: