题意简述：给定 \(n\) 个数 \(a_1,a_2,\dots,a_n\)，要求从这 \(n\) 个数中选出若干组数，使得每组数 \(S_i\) 满足：
- \(|S_i|=k\)；
- 记 \(S_i\) 中元素按降序排序后结果为 \(S_{i,1},S_{i,2},\dots,S_{i,k}\)，则 \(\forall 1\le j，\(S_{i,j}-S_{i,j+1}\ge r\)。此处 \(r\) 预先给定。
求最多能选出多少组这样的数。
\(1\le n\le 10^6\)。
思路：初见本题，很自然地想到一个贪心策略：每次以当前还未被选择的最小值为开头，往后每次选第一个满足比自己大且两数差值 \(\ge r\) 的数作为下一个数，直到选满 \(k\) 个。然后你欣喜地打完代码后发现 WA 了。
Hack:
input:
6 2 2
1 1 3 4 5 6
output:
3
注意到答案具有单调性（此类最优化问题均可以往单调性考虑），因此考虑二分。现在思考 check 函数的实现方式。参照上面的思路，假设当前二分值为 \(mid\)，不难想到以最小的前 \(mid\) 个数作为每组数的开头，随后遍历剩余的每个数，放到第一个可以放的组里，最后看每组的数量是否都 \(\ge k\) 即可。
时间复杂度 \(\mathcal O(n\log n)\)，可以通过本题。
AC CODE：
#includeusing namespace std;typedef long long ll;
typedef unsigned long long ull;
typedef pair pii;const int N = 1e6 + 5;int n, k, r, a[N], b[N];bool check(int mid) {int m = 0, cnt = 0, nowp = 1;for(int i = 1; i <= mid; i++) b[i] = -1e9;for(int i = 1; i <= n; i++) {if(b[nowp] + r <= a[i]) {b[nowp] = a[i];if(nowp == mid) {++cnt, nowp = 1;} else {++nowp;}}}return cnt >= k;
}void solve() {cin >> n >> k >> r;for(int i = 1; i <= n; i++) cin >> a[i];sort(a + 1, a + 1 + n);int l = 0, r = n + 1;while(l + 1 < r) {int mid = l + r >> 1;if(check(mid)) l = mid;else r = mid;}cout << l << endl;
}int main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int T = 1;
// cin >> T;while(T--) solve();return 0;
}