本文共 1526 字，大约阅读时间需要 5 分钟。

牛客小白月赛27 B.乐团派对

题目描述

音乐是带给大家快乐的存在，而你的目标就是组建若干支乐队，让世界听到你们的演奏！

你目前有 $n$ 位乐手，每位乐手只能进入一个乐队，但并不是每位乐手都能担大任，因此需要团队合作。第ii位乐手的能力值为 $a[i]$，表示该位乐手所在乐队的人数必须大于等于 $a[i]$。在保证每位乐手都被分进一个乐队的情况下，乐队数量最多可以是多少？

输入描述:

第一行一个正整数 $n$，表示乐手人数，$n\le 10^5$。

第二行 $n$ 个正整数 $a[i]$，表示每位乐手的能力值，$a[i]\le 10^9$。

输出描述:

输出最多的乐队数量。若无法保证每位乐手都被分进一个乐队，则输出 $-1$。

示例1

输入

42 1 2 1

输出

3

首先这题的出处在这里

由于我之前做过了，所以很快就找到了原题，但是很遗憾，这题是修改过的，原题是不要求所有人都分组求最大组数，而这题的要求所有人都要分组求最大组数，那么我们必须从大往小挑，对某一个位置 $i$，如果 $a[i]>i$，那么肯定输出 $-1$，如果 $a[i]\le i$，就把 $i-=a[i]$，直到 $i=1$ 为止，这样一来很多人都觉得没问题了，其实还有一个坑点，比如：

32 2 2

照上面的分法就是输出 $-1$，其实答案是 $1$，不难发现，当 $i$ 减小后，如果出现 $a[i]>i$，那么此时的 $a[i]$ 可以划分到上一组中而避免无法分组的情况

然后我提交了发现只过 93%，可能是数据加强了，后来找到了一个反例：

74 4 4 4 3 1 1

如果按我的分答案就是 $2$，如果把 $3$ 划分到上一组可以得到 $3$ 组，后来看了题解，这题只能用 DP 解决，我们先对a数组从小到大排序，设 $dp[i]$ 为前 $i$ 个乐手最多能组成的乐队个数，那么有转移方程：

① i<a[i]，dp[i]=0 ② i>=a[i]，dp[i]=max(dp[i-a[i]], dp[i-a[i]-1], …,dp[0])+1 所以我们边转移边维护一个前缀max数组，即可线性求出 $dp[n]$。最后看 $dp[n]$ 是否为 0，若为 0 则输出 -1，否则输出 $dp[n]$。

#include
   
    using namespace std;typedef long long ll;const int N=1e5+5;int n,a[N],mx[N],ans;main(){
       cin>>n;    for(int i=1;i<=n;i++) cin>>a[i];    sort(a+1,a+1+n);    for(int i=1;i<=n;i++){
           if(i>=a[i]) ans=mx[i-a[i]]+1;        else ans=0;        mx[i]=max(mx[i-1],ans);    }    cout<<(ans?ans:-1);}
   

转载地址：https://zaizai.blog.csdn.net/article/details/108179256 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！