题解：P14575 坤班

ZesteYdaZ · 2025-11-23 18:26:10 · 题解

题目链接

https://www.luogu.com.cn/problem/P14575

分析

让愿意当班主任的老师全部当班主任，记班主任数量为 hcnt。同时对于每门学科，记录能教的班级数量和该学科老师中的班主任数量，分别记为 tcnt_{i, 1}, tcnt_{i, 2}。

答案应为班主任数量和最小学科容量中的较小值。

由于可能不需要所有愿意当班主任的老师都当班主任，可以每次找出 tcnt_{i, 1} 最小的学科，若 tcnt_{i, 2} > 0，则令 tcnt_{i, 1} \longleftarrow tcnt_{i, 1} + 1, tcnt_{i, 2} \longleftarrow tcnt_{i, 2} - 1, hcnt \longleftarrow hcnt - 1，即将该学科中一位愿意当班主任的老师置为非班主任以增加学科容量。每次操作后更新答案即可。

细节内容见代码注释。

Code

#include <bits/stdc++.h>

#define int long long

using namespace std;

constexpr int N = 5e5 + 5;
int n, m, a[N][5], hcnt;
pair<int, int> tcnt[N];

// 堆顶学科容量最小 
struct comp
{
    bool operator () (const pair<int, int> &pr1, const pair<int, int> &pr2) const
    {
        return pr1.first > pr2.first;
    }
};
priority_queue<pair<int, int>, vector<pair<int, int> >, comp> hp;

signed main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

    cin >> n >> m;

    for (int i = 1; i <= n; ++ i)
    {
        cin >> a[i][1] >> a[i][2] >> a[i][3];

        // 置为班主任 
        if (a[i][3] == 1)
        {
            ++ hcnt, ++ tcnt[a[i][1]].second;
            -- a[i][2];
        }
        // 更新学科容量 
        tcnt[a[i][1]].first += a[i][2];
    }

    for (int i = 1; i <= m; ++ i)
    {
        hp.push(tcnt[i]);
    }

    int ans = 0;
    for (; !hp.empty();)
    {
        pair<int, int> frt = hp.top();
        hp.pop();

        // 更新答案 
        ans = max(ans, min(hcnt, frt.first));
        // 容量最小的学科没有挽回空间，直接 break 
        if (frt.second == 0 || hcnt < frt.first)
        {
            break;
        }

        // 将本学科中一位班主任置为非班主任 
        ++ frt.first, -- frt.second, -- hcnt;
        hp.push(frt);
    }

    cout << ans << endl;
    return 0;
}