首页 > 试题广场 >

乐团派对

[编程题]乐团派对

热度指数：2796 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

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

输入描述:

第一行一个正整数 $n$ ，表示乐手人数， $n\leq10^{5}$ 。

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

输出描述:

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

示例1

输入

4
2 1 2 1

输出

算法知识视频讲解

溢流眼泪

发表于 2020-08-23 17:36:15

牛客小白月赛27：B题乐团的派对【难度】鄙人不才，WA了8发。。【题意】你有个人，**每个人有能力值，表示该人所在的队伍人数必须大于等于 ** 保证每个人都被分进一个队的情况下，队伍数量最多是多少？无解输出。【数据范围】【样例输入】 42 1 2 1 【样例输出】 3 【解展开全文

璃墨韵

发表于 2020-08-25 10:17:22

设f[i]表示前i个人最多能组成几支乐队对于一个人a[i]，若当前的人数小于a[i]，即他在当前情况下怎样都不能组成乐队，则f[i]=0否则，我们考虑与他组队的人则至少需要a[i]个，我们可以考虑将i-a[i]的人与他分配在一组，此时的f[i]则有i-a[i]钱最大的f值转移过来（中间多的人随便塞展开全文

kilomatutinal

发表于 2026-01-12 01:28:47

咱们有一群小乐手，每个乐手都举着小牌子写着：“我想和至少XX人一起组乐队喵~”喵喵做的第一件事，就是让大家按牌子的数字从小到大排排坐~ 这样才好安排嘛！这时候会出现一个根本不可能的情况：如果那个牌子数字最大的小乐手，他要求的数字比总人数还大……（你这个人满脑子都是自己呢）“喵喵喵？！所有人陪你都不够展开全文

quchen666

发表于 2026-01-12 11:07:12

#include <bits/stdc++.h> using namespace std; const int N=1e5+10; const int mod = 998244353; typedef long long ll; typedef unsigned long long ul 展开全文

bai_qi

发表于 2020-09-07 17:09:14

题目描述音乐是带给大家快乐的存在，而你的目标就是组建若干支乐队，让世界听到你们的演奏！你目前有n位乐手，每位乐手只能进入一个乐队，但并不是每位乐手都能担大任，因此需要团队合作。第i位乐手的能力值为a[i]，表示该位乐手所在乐队的人数必须大于等于a[i]。在保证每位乐手都被分进一个乐队的情况下，乐队展开全文

YunBaichuan

发表于 2026-01-12 11:19:23

思路：这题第一眼贪心，但具体怎么贪就需要仔细想想了。首先可以注意到一个特判，当数组a最大值>数组长度n时，这个最大值无法组乐队，直接输出-1。除此之外的其他情况都可以组乐队，比如最差情况下，所有人一起组一个乐队然后就是怎么贪心了，这个不太好弄，我想了一个多小时，WA了11发才解决。具体流程如展开全文