题意：
把一个数组分成若干组，保证每组的size >= k并且一组中任意两个数字的差的绝对值 <= d，问存不存在这样的分法。
思路：
线性dp。
用dp[i]表示前i个数是否有分法。
设j为满足a[i] - a[j] <= d的最小的a[j]的下标，那么dp[i]就可以从dp[j-1] ~ dp[i-k]转移，j可以二分得到。
首先一定得满足i - k，因为至少有k个数字；
假设前j-1个数字有分法，那么当j - 1 <= i - k的时候，说明第j到第i个数字至少有k个数字并且a[i] - a[j] <= d。
但是从j-1到i-k扫一遍要花费O(n)的时间，所以需要维护一个前缀和，判断的时候只需要j -1 <= i - k 并且pre[i-k] - pre[j-2] > 0，就说明从j - 1到i - k这个区间内有满足的分法。
代码：
1 #include <stdio.h> 2 #include <string.h> 3 #include <algorithm> 4 using namespace std; 5 const int N = 5e5 + 10; 6 int a[N]; 7 int dp[N]; 8 int pre[N]; 9 int main() 10 { 11 int n,k,d; 12 scanf("%d%d%d",&n,&k,&d); 13 for (int i = 1;i <= n;i++) 14 { 15 scanf("%d",&a[i]); 16 } 17 sort(a+1,a+n+1); 18 if (a[k] - a[1] <= d) dp[k] = 1; 19 pre[k] = dp[k] + 1; 20 dp[0] = 1; 21 pre[0] = 1; 22 for (int i = k + 1;i <= n;i++) 23 { 24 int en = i - k; 25 int l = 1,r = i; 26 while (r - l > 1) 27 { 28 int mid = (l + r) >> 1; 29 if (a[i] - a[mid] <= d) r = mid; 30 else l = mid + 1; 31 } 32 while (r > 1 && a[i] - a[r-1] <= d) r--; 33 int st = r; 34 if (st == 1) dp[i] = 1; 35 else if (st-1 <= en) if (pre[en] - pre[st-2] > 0) dp[i] = 1; 36 pre[i] = pre[i-1] + dp[i]; 37 } 38 if (dp[n]) puts("Yes"); 39 else puts("No"); 40 return 0; 41 }
codeforces 985E Pencils and Boxes
原文：https://www.cnblogs.com/kickit/p/9070868.html