题解：CF1133E K Balanced Teams

Clover_Lin · 2025-05-01 17:46:14 · 题解

思路

发现这个具有单调性，考虑二分答案。

我们默认数组已经从小到大排序了。

令 f_i 表示 i 前面最靠前的能和他组成一队的人的编号，这个直接二分查找就做出来了。

接下来，我们写一个 DP：令 mx_{i,j} 表示考虑前 i 个，最多分 j 个队的最大人数。转移方程：mx_{i,j}=\max_{p=1}^{f_i-1}mx_{i,j-1}+i-f_i+1。然后 呢，我们发现那重循环不可避免地超时了。于是使用 pre_{i,j} 表示 \max_{p=1}^{i}mx_{p,j}，把循环用数组替代了。

二分答案的检查函数怎么写呢？我们直接判断 \max_{mid}^n mx_{i,k}\ge 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 19

20 2
1 1 3 3 4 5 7 7 7 8 10 11 12 13 14 15 16 17 18 18
*/