给出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