P2062 分队问题 题解

题目大意

有 \(N\) 名选手， 现在要把他们分到若干队，每个选手要求他的队伍的人数必须要大于等于 \(a_i\), 求最多可以分多少个队伍。

确定算法

贪心思想

这道题没有标签，差评，初次看题没有任何思路，看到最大化队伍数量就想到了贪心,。

在打代码的过程中发现贪心会发生错误， 每次贪心后并没有考虑到后面的人对队伍的限制，没有满足最优决策。 兴致勃勃的证明了半天贪心错误， 题解里有人证出来了？？？？

DP思想

话说贪心和DP总是在一起的，既然贪心错误那就DP！

首先考虑定义的状态，用 \(f{[i]}\) 表示前 \(i\) 个人中最大的队伍数量。

那么阶段就是 \(1\) 到 \(N\)。
答案就是 \(f[n]\)。

使用DP解决这道题目

首先我们要进行排序， 保证决策的正确（这不就是贪心吗？）

可以先特判一下， 如果要求的最大的人数都大于了总人数，直接输出 \(0\)。

分 \(2\) 种情况讨论， 第一种情况是当前人数不大于 \(i\)，另外一种是人数大于等于 \(i\)。

当前的 \(a[i]\) 不大于 \(i\) ， 就只有一个决策

\[f[i] = f[i - 1] \]

反之当前的 \(a_i \leq i\) 了，即有 \(2\) 个决策, 要么加， 要么不加。

转移方程就是

\[f[i] = max(f[i- 1], f[i - a[i] + 1) \]

应该很好推吧

代码

#include<bits/stdc++.h>

using namespace std;
inline int read() {
	int x = 0, f = 1; char ch = getchar();
	while (ch < '0' || ch > '9') f |= ch == '-' ? 1 : -1, ch = getchar();
	while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
	return x;
}
inline void print(int x){
	char P[105];int w=0;if(x==0){putchar('0');return;}
	if(x<0) putchar('-'),x=-x;
	while(x) P[++w]=x%10+'0',x/=10;
	for(int i=w; i>=1; i--) putchar(P[i]);
}

const int N = 1e6;
int n, a[N + 1], ans, f[N + 1];
int main() {
	n = read();
	for (int i = 1; i <= n; i++) a[i] = max(1, read());
	sort(a + 1, a + n + 1);
	if (a[n] > n) {
		puts("0");
		return 0;
	}
	for (int i = 1; i <= n; i++) {
		if (a[i] > i) f[i] = f[i - 1];
		else f[i] = max(f[i - 1], f[i - a[i]] + 1);
	}
	print(f[n]);
	return 0;
}