乐***对-题解

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

你目前有n位乐手，每位乐手只能进入一个乐队，但并不是每位乐手都能担大任，因此需要团队合作。第i位乐手的能力值为a[i]，表示该位乐手所在乐队的人数必须大于等于a[i]。在保证每位乐手都被分进一个乐队的情况下，乐队数量最多可以是多少？
思路：按照能力值排序，然后大概就找需要人少的。详见代码。

代码：

#include <bits/stdc++.h>
using namespace std;
int dp[100005],b[100005];
struct Node{
    int pos;
    int l,x;
}a[100005];
bool cmp(Node c,Node d)
{
    return c.l>d.l;
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)scanf("%d",&b[i]);
    sort(b,b+n);
    int maxn=0;
    for(int i=0;i<n;i++){
        int x=b[i];
        a[i].pos=i;
        a[i].l=i-x;
        a[i].x=x;
        maxn=max(x,maxn);
    }
    sort(a,a+n,cmp);
    if(maxn>n){
        printf("-1\n");
        return 0;
    }
    int i=0;
    for(i=0;i<n;i++)if(a[i].x==maxn)break;
    int l=a[i].l,ans=1;
    i++;
    while(i<n){
        if(a[i].pos<=l){
            ans++;
            l=a[i].l;
        }
        //printf("%d %d\n",l,ans);
        i++;
    }
    if(l!=-1)ans--;
    printf("%d\n",ans);
    return 0;
}