E. Pencils and Boxes（树状数组+dp）

E. Pencils and Boxes（树状数组+dp）

E. Pencils and Boxes

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Mishka received a gift of multicolored pencils for his birthday! Unfortunately he lives in a monochrome world, where everything is of the same color and only saturation differs. This pack can be represented as a sequence a1, a2, ..., an of n

Each pencil belongs to exactlyEach non-empty box has at leastkIf pencilsiandjbelong to the same box, then |ai-aj| ≤d, where |x| means absolute value ofx. Note that the opposite is optional, there can be pencilsiandjsuch that |ai-aj| ≤d

Help Mishka to determine if it's possible to distribute all the pencils into boxes. Print "YES" if there exists such a distribution. Otherwise print "NO".

Input

The first line contains three integer numbers n, k and d (1 ≤ k ≤ n ≤ 5·105, 0 ≤ d ≤ 109) — the number of pencils, minimal size of any non-empty box and maximal difference in saturation between any pair of pencils in the same box, respectively.

The second line contains n integer numbers a1, a2, ..., an (1 ≤ ai ≤ 109) — saturation of color of each pencil.

Output

Print "YES" if it's possible to distribute all the pencils into boxes and satisfy all the conditions. Otherwise print "NO".

Examples

Copy

6 3 10 7 2 7 7 4 2

Copy

YES

Copy

6 2 3 4 5 3 13 4 10

Copy

YES

Copy

3 2 5 10 16 22

Copy

NO

题目大概：

给出n个数，要求给这些数分组，每组不少于k个。每组的数之间的差不能大于d。是否能够分组？

思路：

可以考虑排序后，用dp。dp【i】代表1到i是否可以分组成功。

dp【i】能否分组，取决于dp【j】到dp【i-k+1】；dp【j】代表最小的一个与i差值小于d的。

如果dp【j】到dp【i-k+1】有一个是可以分组成功的，那dp【i】也可以分组成功。

但是如果直接两重for求解的话，会超时。所以，用树状数组来统计一下1到n可以分组的数的数量。

代码：

#include using namespace std;const int maxn=500005;int a[maxn];int dp[maxn];int c[maxn];int lowbit(int x){ return x&(-x);}void add(int x,int v){ while(x<=maxn) { c[x]+=v; x+=lowbit(x); }}int sum(int x){ int sum=0; while(x>0) { sum+=c[x]; x-=lowbit(x); } return sum;}int get(int l,int r){ if(l>r)return 0; else return sum(r)-sum(l-1);}int main(){ int n,k,d; scanf("%d%d%d",&n,&k,&d); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); } sort(a+1,a+n+1); dp[1]=1; add(1,1); int l=1; for(int i=2;i<=n;i++) { while(ld)++l; dp[i+1]=(get(l,i-k+1)>=1); if(dp[i+1])add(i+1,dp[i+1]); } if(dp[n+1]) { printf("YES\n"); } else printf("NO\n"); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。