首页 > 其他分享 >Pencils and Boxes CF985E

Pencils and Boxes CF985E

时间:2023-03-26 17:35:45浏览次数:32  
标签:Pencils CF985E int Boxes inf include

给出nn个整数a1,a2,...,an,现在需要对其进行分组,使其满足以下条件:

  • 每个数都必须恰好分入一组中

  • 每一组中必须至少包含K个数

  • 在每一组中,整数的权值之差的绝对值<=D。

请判断是否存在满足条件的分组方案,若有请输出"YES",否则输出"NO"。

 

直接的贪心是错误的,但要魔改一下,双指针+dp,

F [i ] = 0 / 1

然后刷表法,双指针写法

 

#include<iostream>
#include<algorithm> 
#include<cstring>
#define IOS std::ios::sync_with_stdio(0)
using namespace std;
 #define inf 1e9 
 const int  N= 1e6+5;
 int a[N],n,K,D ,f[N] ;
 signed main(){
 	int i,j;
 	cin>>n>>K>>D;
 	for(i=1;i<=n;i++) cin>>a[i];
 	sort(a+1,a+1+n);
 	
 	a[n+1]=  inf;
 	f[0]=1;
 	j=1;
 	for(i=0;i<=n;i++){
 		if(f[i]){
 			j=max(j,i+K) ; if(j>n) break;
 			while(a[j]-a[i+1]<=D) f[j]=1,j++;
 		}
 	}
 	cout <<(f[n]?"YES":"NO");
 }
 
 
 

 

标签:Pencils,CF985E,int,Boxes,inf,include
From: https://www.cnblogs.com/towboa/p/17259023.html

相关文章