牛客小白月赛27：B题 乐团的派对

【难度】

鄙人不才，WA了8发。。

【题意】

你有 个人，**每个人有能力值 ，表示该人所在的队伍人数必须大于等于 **

保证每个人都被分进一个队的情况下，队伍数量最多是多少？无解输出。

【数据范围】

【样例输入】

4
2 1 2 1

【样例输出】

3

【解释】

队伍1：第一个人、第三个人
队伍2：第二个人
队伍3：第三个人

【思路】

（一）首先考虑贪心

首先判断可行性。易得，若 则无解，输出。
接下来，人怎么分组？
既然是贪心，易想到我们需要对能力值进行排序。

（1）逆序贪心？

【做法】
我们把 从 到 进行循环遍历。
若对于第 个人能力值为 是接下里还没分好组的人。
接下来，我们选择 ，把这些人组成一支队伍。
若 ，则可以划分队伍，因为易得
若，则无法划分队伍，就把他们合并到人数最多的队伍。

【结果】
可以AC

有反例可以
比如
按照该贪心算法，分组为，为两组。
但是正确的分组应该为 ，为六组。
牛客数据水了

【结论】

（2）顺序贪心？

【做法】
我们把 从 到 进行循环遍历。
若对于第 个人能力值为 是接下里还没分好组的人。
接下来，我们选择 ，把这些人组成一支队伍。
若，则无法划分队伍，就把他们合并到人数最多的队伍。

【结果】

该算法。 当然不一定成立。
比如分组
按该算法的分组为 ，为两组。但是分组不满足题目要求呀！
但是正确的分组应该为 ，为一组。

【结论】

（3）改良顺序贪心？

【做法】
我们把 从 到 进行循环遍历。
若对于第 个人能力值为 是接下里还没分好组的人。
接下来，我们选择 ，把这些人组成一支队伍。
若 ，我们继续选择
直到第一个合法的 满足
若 找不到合法的 ，则这些人与最大人数的队伍合并。

该算法。
比如分组
按该算法， 枚举到时，目前分组为 。
但是遇到 ，我无法选出5个人来，也无法在某个已有团队中直接把这个人给塞进去。
我们还要再计算最少数目的已有团队，使得团队总人数
怎么变成背包问题了？？这可是贪心做法！

【结论】

（4）正解贪心

【做法】

升序排序后，**我们先把 安排掉**，易得至少要 个人。
我们安排 这些下标的人： 成立，所以该选择一定是合法的、最贪心的。

接下来，我们把 从 到 进行循环遍历。与做法3的贪心选择相同：

若对于第 个人能力值为 是接下里还没分好组的人。
接下来，我们选择 ，把这些人组成一支队伍。
若 ，我们继续选择
直到第一个合法的 满足
若 找不到合法的 ，则这些人与最大人数的队伍合并。

【核心代码】

时间复杂度：
就是排序+for循环的时间复杂度。

/*
 _            __   __          _          _
| |           \ \ / /         | |        (_)
| |__  _   _   \ V /__ _ _ __ | |     ___ _
| '_ \| | | |   \ // _` | '_ \| |    / _ \ |
| |_) | |_| |   | | (_| | | | | |___|  __/ |
|_.__/ \__, |   \_/\__,_|_| |_\_____/\___|_|
        __/ |
       |___/
*/
const int MAX = 1e5+50;
int aa[MAX];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",&aa[i]);
    sort(aa+1,aa+1+n);
    int ren = 1;            /// ren表示目前该队伍中有多少人，默认值为 1
    int ans = 1;
    if(aa[n] > n)printf("-1");
    else{
        for(int i=1;i<=n - aa[n];++i){
            while(i<=n - aa[n] && ren < aa[i]){
                int cha = aa[i] - ren;
                ren += cha;
                i += cha;
            }
            if(i > n - aa[n])break;    /// 找不到合法的‘k’，与最大队伍合并，答案不变
            ans++;            /// 找到了合法的‘k’，新的队伍产生
            ren = 1;
        }
        printf("%d",ans);
    }
    return 0;
}

（二）其次考虑DP做法

首先，我们一样升序排序。
对于第 个人我们可以把它合并在第 个人的团队里面（如果存在的话）。
或者，我们**选择 下标的人拉成新的一个队伍**。
当然这时我们选择的是 ，稍微想一想就能得到了。

那么状态转移方程就得到了：

【感谢热心网友的Hack！】

【核心代码】

时间复杂度：
就是排序+for循环的时间复杂度。
人的本质是复读机

/*
 _            __   __          _          _
| |           \ \ / /         | |        (_)
| |__  _   _   \ V /__ _ _ __ | |     ___ _
| '_ \| | | |   \ // _` | '_ \| |    / _ \ |
| |_) | |_| |   | | (_| | | | | |___|  __/ |
|_.__/ \__, |   \_/\__,_|_| |_\_____/\___|_|
        __/ |
       |___/
*/
const int MAX = 2e5+50;
int aa[MAX];
int dp[MAX];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",&aa[i]);
    sort(aa+1,aa+1+n);
    int t;
    for(int i=1;i<=n;++i){
        int di = (i - aa[i]);
        t = 0;                        /// 选 [di+1,i]的人的时候的dp[i]的值
        if(di >= 0)t = dp[di] + 1;
        dp[i] = max(t,dp[i-1]);       /// 向左合并
    }
    printf("%d",t==0 ? -1 : t);       /// 为了保证合法，最后一支队伍要选择区间[n-a[n]+1,n]的范围
    return 0;
}