Codeforces
题意：
给定n支铅笔，问能不能分成若干堆，使得每堆数量不小于k且每堆的最大值和最小值之差不大于d。
题解：
排序。从后往前扫一遍。考虑以每个点为最小值建堆是否合法。对于当前点i，它需要至少k支铅笔，但是最大值不超过a[i]+d，所以就会有一个成立的范围[l,r]。假设存在点k(l<=k<=r)，使得k+1这个位置建堆是合法的，那么点i建堆也是合法的。用树状数组维护[l+1,r+1]中的建堆合法个数。
#include <bits/stdc++.h> using namespace std; int n, k, d; int a[500005], tre[500005]; int vis[500005]; void add(int x) { while(x <= n) { tre[x]++; x += x&(-x); } } int sum(int x) { int res = 0; while(x>0) { res += tre[x]; x -= x&(-x); } return res; } int main() { scanf("%d%d%d", &n, &k, &d); for(int i = 1; i <= n; i++) scanf("%d", &a[i]); sort(a+1, a+n+1); for(int i = n-k+1; i >= 1; i--) { int l = i+k-1, r = upper_bound(a+i, a+n+1, a[i]+d)-a-1; if((r>=n) || (r>=l&&sum(r+1)-sum(l)>0)) vis[i] = 1; if(vis[i]) add(i); } if(vis[1]) puts("YES"); else puts("NO"); }