题解：CF1133E K Balanced Teams

思路

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

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

令

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

是否成立即可。

代码

CPP

#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
*/

题解：CF1133E K Balanced Teams

文章操作

思路

代码

相关推荐

评论

题解：CF1133E K Balanced Teams