题解：P14575 坤班

jaspersgr · 2025-11-23 18:51:38 · 题解

拿到题面先看一眼设问，看到最多，容易想到二分。我们考虑二分班级数量。

接下来考虑二分中的 check。

• 用 s 数组记下每个科目分别可以教多少个班（就是把教某一科目的老师可以教的班的总和），方便后面算出空余的老师数量
• 再统计一下每个科目老师里面可以当班主任的老师数量，这样就可以避免一下当不了班主任的老师当班主任了。

下面是 check 部分的代码

int s[200005], bzr[200005]; //bzr 记的是每个科目老师里面可以当班主任的老师数量
bool ck(int x)
{
    int cnt = 0; // 记的是所有科目里面分配出来可以当班主任的老师数量
    for (int i = 1; i <= m; i++)
    {
        cnt += min(s[i] - x, bzr[i]); //既要有空闲的老师，又要能当班主任
    }
    return cnt >= x; // 是否能每个班级都配备一个班主任
}

再来看看二分。

左边界毋庸置疑，肯定是 1。但是右边界的限制比较多了。

第一眼看到肯定是小于所有的班主任数量，但是这样只能拿 5 分。

另一个限制就是右边界必须小于 s_i 中的任意值。

以上就是全部要点了，下面是代码，禁止抄袭！

code

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, m;
int a[500005], b[500005], c[500005];
int s[500005], bzr[500005];
bool ck(int x)
{
    int cnt = 0;
    for (int i = 1; i <= m; i++)
    {
        cnt += min(s[i] - x, bzr[i]);
    }
    return cnt >= x;
}
signed main()
{
    cin >> n >> m;
    int cnt = 0;
    int mn = 1e9;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i] >> b[i] >> c[i];
        s[a[i]] += b[i];
        bzr[a[i]] += c[i];
        cnt += c[i];
    }
    for (int i = 1; i <= m; i++)
        mn = min(mn, s[i]);
    int l = 1, r = min(mn, cnt);
    while (l <= r)
    {
        int mid = (l + r) >> 1;
        if (ck(mid))
            l = mid + 1;
        else
            r = mid - 1;
    }
    cout << r << endl;
}

以上就是本篇题解的全部内容了。