2 seconds
256 megabytes
standard input
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 integer numbers — saturation of the color of each pencil. Now Mishka wants to put all the mess in the pack in order. He has an infinite number of empty boxes to do this. He would like to fill some boxes in such a way that:
- Each pencil belongs to exactly one box;
- Each non-empty box has at least k pencils in it;
- If pencils i and j belong to the same box, then |ai - aj| ≤ d, where |x| means absolute value of x. Note that the opposite is optional, there can be pencils i and j such that |ai - aj| ≤ d and they belong to different boxes.
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".
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.
Print "YES" if it's possible to distribute all the pencils into boxes and satisfy all the conditions. Otherwise print "NO".
6 3 10
7 2 7 7 4 2
YES
6 2 3
4 5 3 13 4 10
YES
3 2 5
10 16 22
NO
In the first example it is possible to distribute pencils into 2 boxes with 3 pencils in each with any distribution. And you also can put all the pencils into the same box, difference of any pair in it won't exceed 10.
In the second example you can split pencils of saturations [4, 5, 3, 4] into 2 boxes of size 2 and put the remaining ones into another box.
【题意】
给$$$n$$$个数，可以放到若干个盒子里，要求每个盒子至少有$$$k$$$个数，并且每个盒子中最大和最小的数差值不超过$$$d$$$。问是否有合理的方案来分配。
【分析】
因为要比较差值，所以按从小到大对输入排序，如果$$$a_i$$$和$$$a_j$$$已经放到同一个盒子里了，那么大小介于$$$a_i$$$和$$$a_j$$$之间的数也一定可以放到这个盒子中。
由于上述的性质，每个盒子都应该装$$$a_i$$$~$$$a_j$$$的全部数。因为$$$a_i$$$和$$$a_j$$$是离其他数最近的数，如果现在的分配不可行，一定是先把$$$a_i$$$或$$$a_j$$$重新划分给相邻的盒子，成为新的区间端点，而整个方案依然的连续的；而如果$$$a_i$$$和$$$a_j$$$不能分配给其他盒子，那么内部的其他数也一定不行。从另一方面来说，如果把一个$$$a_i$$$~$$$a_j$$$中的一个$$$a_x$$$拿出去，最终形成了可行方案，那么一定可以通过把$$$a_x$$$与$$$a_i$$$或$$$a_j$$$交换，使方案依然可行而且每个盒子中变成连续的区间。
连续分配说明完了，之后都把盒子当作区间来处理，问题转化为：把1~n个数分为几个连续的区间，使的每个区间$$$[a_i, a_j]$$$的$$$a_j-a_i \le d, j-i \ge k$$$。
预处理：对于每个$$$a_i$$$一定有一个最大的$$$a_j$$$，用二分查找得到其下标，并把$$$a_j$$$下一个位置也就是$$$j+1$$$记录到$$$right[i]$$$ (下面会介绍) 中。
如果一个盒子是$$$[a_i, a_j]$$$那么下一个盒子的起点就是$$$a_{j+1}$$$。可以把从$$$a_i$$$到$$$a_{j+1}$$$看成一次转移，这样重复下去，如果最后刚好能到达数列的末端，那么从$$$a_i$$$开始就是可行的，$$$a_i$$$就是能到末端的点。这个时候$$$right[i]$$$数组就发挥作用了，对于$$$a_i$$$，它能转移到的起点有 $$$a_{i+k}, a_{i+k+1}, ...,a_{right[i]}$$$;
dp可以采取从后向前的顺序。在考虑$$$a_i$$$作为起点时，它可以转移到的点都在它后面，所以$$$[a_{i+k}, a_{right[i]}]$$$都处理过了，只要其中包含末端，或者能到末端的点，那么$$$a_i$$$也是能到达末端的点；如果区间不存在，或者不包含能到末端的点，那么$$$a_i$$$就不能到达末端。这样从后向前处理完所有点以后，起点能否到达末端就是答案的YES/NO。
如果用0表示无法到达末端，1表示能到达末端，那么转移方程就是：
$$$$$$dp[i]= (\sum_{j=i+k}^{right[i]} dp[j]) \gt 0$$$$$$
起始状态为$$$dp[n]$$$=$$$1$$$。
【注意】
使用树状数组来完成求和操作，下标的起点必须是1。
#include<stdio.h>
#include<algorithm>
using std::sort; #define N_max 500005
int ipt[N_max], right[N_max]; int n, k, d;
int cmpv(int t1, int t2) {
return t1 < t2;
}
void cal_r(int i) {
if (right[i] != 0)return;
int l = i, r = n + 1, m;
while (l + 1<r)
{
m = (l + r) / 2;
if (ipt[m] <= ipt[i] + d)l = m;
else r = m;
}
right[i] = r;
}
struct BIT {
int c[N_max] = { 0 };//每个ci维护的都是1~i的最新和
int lowbit[N_max] = { 0 };
int n;
BIT(int _n = N_max) {
n = _n;
for (int i = 1; i <= N_max; ++i) lowbit[i] = (i&(-i));
}
void newBIT(int _n) {
n = _n;
for (int i = 1; i <= n; ++i)
c[i] = 0;
}
//更新时向右（上）更新
void update(int x, int num) {
while (x <= n) {
c[x] += num;
x += lowbit[x];
}
}
//求和时向左（下）依次求和
int getsum(int x) {
int s = 0;
while (x > 0) {
s += c[x];
x -= lowbit[x];
}
return s;
}
}bit;
int main() {
scanf("%d %d %d", &n, &k, &d);
bit.newBIT(n+1);
for (int i = 1; i <= n; ++i)
scanf("%d", ipt + i); sort(ipt + 1, ipt + n + 1, cmpv);
int state;
//初始状态为只有末端可以到达末端
bit.update(n + 1, 1);
//计算right[i]
for (int i = 1; i <= n; ++i)
cal_r(i);
//从后向前dp
for (int i = n; i >= 1; --i)
{
if (i + k - 1 <= n)//至少存在一个
{
//使用树状数组判断区间内是否有不为0 的值
state = (bit.getsum(right[i]) - bit.getsum(i + k - 1)) > 0;
bit.update(i, state);
}
}
state = bit.getsum(1);
printf("%s", state == 1 ? "YES" : "NO");
return 0;
}