首页 > 试题广场 >

乐团派对

[编程题]乐团派对

热度指数：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

输出

算法知识视频讲解

Python3

驴主

组乐队真开心啊！

排序 + 贪心 + DP

首先，最棘手的家伙是那个能力值最大的。如果她没法被满足，那就无解；而如果她能被满足，则一定有解。因为她的乐队可以当做一个「垃圾桶」，不想要的乐手都可以丢进去。

为了满足能力值最大的家伙，我们需要帮她找若干小伙伴。显然这些小伙伴的能力值越大越好。把棘手的家伙们都解决掉，更有利于我们后续的选择。

接下来就可以进入 DP 环节。详见代码：

n = int(input())
arr = list(map(int, input().split()))
arr.sort()
# 无解
if arr[-1] > n:
    print(-1)
# 只能组一个乐队
elif arr[-1] == n:
    print(1)
else:
    # 先贪心地把「垃圾桶」乐队组出来
    arr = arr[:-arr[-1]]
    n = len(arr)
    # dp[i] 表示用前 i + 1 个乐手组乐队的最优结果
    dp = [0] * n 
    dp[0] = 1 if arr[0] == 1 else 0
    for i in range(1, n):
        # 有两种选择：
        # ① 当前乐手丢进垃圾堆，用前面 i - 1 个乐手组乐队
        dp[i] = dp[i - 1]
        # ② 如果能满足当前乐手：贪心地为她组一个乐队，然后用剩下乐手继续组乐队
        if arr[i] <= i + 1:
            dp[i] = max(dp[i], dp[i - arr[i]] + 1)
    print(dp[-1] + 1)

发表于 2026-01-12 07:45:33 回复(2)

提交观点

问题信息

难度：

1条回答 16收藏 185浏览

乐团派对

输入描述:

输出描述:

输入

输出

组乐队真开心啊！

问题信息

热门推荐

相关试题