题解 | 乐团派对

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e5 + 5;
ll a[N];  // 存储每个乐手的能力值
ll f[N];  // DP数组：f[i]表示前i个乐手能组成的最大乐队数量

int main() {
    // 步骤1：输入优化，关闭cin与stdio同步、解除cin绑定cout，加速输入输出
    ios::sync_with_stdio(0), cin.tie(0);

    // 步骤2：读取输入数据
    ll n;          // 乐手总数量
    cin >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> a[i];  // 读取第i个乐手的能力值（能力值要求：乐队人数≥该值）
    }

    // 步骤3：排序预处理——将能力值从小到大排序
    // 核心思想：小能力值的乐手更容易满足“乐队人数≥能力值”，优先处理可最大化分组数
    sort(a + 1, a + n + 1);

    // 步骤4：合法性预判——剪枝优化
    // 若最大能力值超过总人数，必然无法组成满足该乐手的乐队，直接输出-1
    if (a[n] > n) {
        cout << -1;
        return 0;
    }

    /*
    当第i个乐手的能力值 ≤ 前i个乐手的总数时(i)
    此时发f[i]的状态由 f[i-1] 的状态（该乐手加入上一名乐手的乐队）和 f[i - a[i]] + 1 的状态(该乐手与包括自己的往前a[i]名乐手组成一个乐队）的最大值决定
    */

    // 步骤5：动态规划核心——状态转移计算
    for (ll i = 1; i <= n; i++) {
        // 条件：第i个乐手的能力值 ≤ 前i个乐手的总数（说明有可能凑出满足该能力值的乐队）
        if (a[i] <= i) {
            // 状态转移方程：
            // 两种选择取最大值：
            // 1. 不使用第i个乐手分组 → 继承前i-1个的最优解 f[i-1]
            // 2. 使用第i个乐手分组 → 前i-a[i]个的最优解 + 1个新乐队（凑够a[i]人组成1个乐队）
            f[i] = max(f[i - 1], f[i - a[i]] + 1);
        }
        else {
            // 若能力值超过前i个乐手总数，前i个无法组成有效乐队，重置为0
            f[i] = 0;
        }
    }

    // 步骤6：输出结果——前n个乐手可组成的最大乐队数量
    cout << f[n];
    return 0;
}