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;
}
推荐阅读
-
Codeforces - Pencils and Boxes
-
Okabe and Boxes(栈)
-
E - Okabe and Boxes
-
Educational Codeforces Round 41 (Rated for Div. 2) E. Tufurama(树状数组+偏序)
-
Educational Codeforces Round 37 (Rated for Div. 2) E. Connected Components?(图论+连通块+bfs)
-
Educational Codeforces Round 66 (Rated for Div. 2)-E. Minimal Segment Cover
-
Educational Codeforces Round 65 (Rated for Div. 2) E. Range Deleting(双指针+思维)
-
Educational Codeforces Round 66 (Rated for Div. 2) E. Minimal Segment Cover 倍增
-
Codeforces Round #226 (Div. 2)
-
Codeforces Round #FF (Div. 2) D. DZY Loves Modification 贪心+优先队列_html/css_WEB-ITnose