题解：P14575 坤班

zy_oier · 2025-11-23 18:36:57 · 题解

思路

考虑二分查找班级的个数。

先统计每个学科的任课老师所教班级总数与愿意当班主任的老师总数，确定班级上界。

check函数中遍历所有老师，若老师同意当班主任且这个老师去当班主任不会让此科目可以教授的班级数量过少，就让这个老师去当班主任，最后判断班主任个数够不够。

代码

#include<bits/stdc++.h>
#define f(n) for(int i=1;i<=n;i++)
#define int long long
#define endl "\n" 
#define IOS cin.tie(0),cout.tie(0),ios::sync_with_stdio(0)
using namespace std;
int n,m,sum,minx=INT_MAX,l,r,mid,bzr,s[500005],ss[500005];
struct T{int a,b,c;}t[500005];
int check(int x){
    memcpy(ss,s,sizeof(s));
    bzr=0;
    f(n)if(t[i].c)if(ss[t[i].a]>x)bzr++,ss[t[i].a]--;
    //若老师同意当班主任且老师去当班主任不会让其科目可以教授的班级数量过少，就让这个老师当班主任 
    return bzr>=x;
}
signed main(){
    IOS;cin>>n>>m;
    f(n)cin>>t[i].a>>t[i].b>>t[i].c,sum+=t[i].c,s[t[i].a]+=t[i].b;//统计每个学科可以教的班数 
    f(m)minx=min(minx,s[i]);
    minx=min(minx,sum);//确定班级上界 
    l=0,r=minx;//标准的二分 
    while(l<r){
        mid=(l+r+1)/2;
        if(check(mid))l=mid;
        else r=mid-1;
    }
    cout<<l;
    return 0;
}