题解：CF1133E K Balanced Teams
思路
发现这个具有单调性，考虑二分答案。
我们默认数组已经从小到大排序了。
令 f i f_i fi 表示 i i i 前面最靠前的能和他组成一队的人的编号，这个直接二分查找就做出来了。
接下来，我们写一个 DP：令 m x i , j mx_{i,j} mxi,j 表示考虑前 i i i 个，最多分 j j j 个队的最大人数。转移方程： m x i , j = max p = 1 f i − 1 m x i , j − 1 + i − f i + 1 mx_{i,j}=\max_{p=1}^{f_i-1}mx_{i,j-1}+i-f_i+1 mxi,j=maxp=1fi−1mxi,j−1+i−fi+1。然后 呢，我们发现那重循环不可避免地超时了。于是使用 p r e i , j pre_{i,j} prei,j 表示 max p = 1 i m x p , j \max_{p=1}^{i}mx_{p,j} maxp=1imxp,j，把循环用数组替代了。
二分答案的检查函数怎么写呢？我们直接判断 max m i d n m x i , k ≥ m i d \max_{mid}^n mx_{i,k}\ge mid maxmidnmxi,k≥mid 是否成立即可。
代码
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;int n, k;
int a[5010], f[5010];
int mx[5010][5010];
int pre[5010][5010];bool check(int mid)
{for (int i = mid; i <= n; i++)if (mx[i][k] >= mid)return true;return false;
}int main()
{cin >> n >> k;for (int i = 1; i <= n; i++)cin >> a[i];sort(a + 1, a + n + 1);a[0] = -1e9;for (int i = 1; i <= n; i++)f[i] = lower_bound(a + 1, a + i + 1, a[i] - 5) - a;for (int i = 1; i <= k; i++){mx[1][i] = 1;pre[1][i] = 1;}for (int i = 2; i <= n; i++)for (int j = 1; j <= k; j++){mx[i][j] = max(i - f[i] + 1, pre[f[i] - 1][j - 1] + i - f[i] + 1);pre[i][j] = max(pre[i - 1][j], mx[i][j]);
// cout << i << ", " << j << ": " << mx[i][j] << endl;}int l = 0, r = n;while (l < r){int mid = l + r + 1 >> 1;if (check(mid))l = mid;else r = mid - 1;}cout << l << endl;return 0;
}
/*
20 2
1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1920 2
1 1 3 3 4 5 7 7 7 8 10 11 12 13 14 15 16 17 18 18
*/