题目描述

给定n个选手，将他们分成若干只队伍。其中第i个选手要求自己所属的队伍的人数大等于a[i]人。

在满足所有选手的要求的前提下，最大化队伍的总数。

注：每个选手属于且仅属于一支队伍。

输入格式

第一行一个整数n，表示人数。

以下n行，每行一个整数表示a[i]。

输出格式

输出队伍总数的最大值。数据保证有解。

输入输出样例

输入 #1

1
2
3
4
5
6

5
2
1
2
2
3 

输出 #1

1

2

说明/提示

对于20%的数据，n <= 10

对于40%的数据，n <= 1000

对于60%的数据，n <= 10000

对于100%的数据，1 <= n <= 10^6

解析

第一反应是个贪心

就是从大往小排序，然后从前往后扫，每碰到一个人就把它后面的人都拉进队

每个元素只会访问一次，时间复杂度

但是这个是错的

考虑这组数据：

1

n = 4, a[] = { 2, 3, 3, 3 }

贪心跑出来是 2，答案应该是 3
原因在于贪心无法判断当前的人是另开一队更优还是加入已有队伍更优，赛后我看了一眼洛谷题解，有人判了这个之后贪心过了但我没看懂

考虑 dp

首先把 a[] 从小到大排个序

然后设 f[i] 表示当前安排了前 i 个人所能获得的最大队伍数
转移方程：

就是，对于一个人，可以把他塞进旧队伍里，也可以接着前面的 个人开一个新队伍

时间复杂度

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

//
// Created by HandwerSTD on 2019/11/1.
// Copyright (c) 2019 HandwerSTD. All rights reserved.
// Title: 分队问题
//
// sto Qingyu orz
// 感谢真神sqy无私的教诲。膜时队者处处阿克，只因大师sqy在他背后。不膜大师者违背了真神的旨意，真神必将降下天谴，
// 使其天天爆零
// 我不由自主地膜拜真神sqy。
//

#include <cstdio>
#include <algorithm>
#include <functional>

const int MAXN = 1e6 + 10;

int n, arr[MAXN], f[MAXN];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", arr + i);
    std::sort(arr + 1, arr + 1 + n);
    for (int i = 1; i <= n; ++i) {
        if (i < arr[i]) f[i] = f[i - 1];
        else f[i] = std::max(f[i - 1], f[i - arr[i]] + 1);
    }
    printf("%d\n", f[n]);
    return 0;
}