题解：P14575 坤班

leather_handbag · 2025-11-23 19:17:45 · 题解

考虑二分班级数量，设二分到的答案为 x，则需要满足两个条件：

1. 当班主任的人数 \ge x。

2. 设 f_i 表示学科 i 能教到 f_i 个班级，则 \min_{i=1}^nf_i\ge x。

设 num_i 表示教学科 i 的老师有多少愿意当班主任，则对于每个学科，已知二分班级 x，可以得到这个学科最多能有 \min(num_i,f_i-x) 个老师当班主任。

代码

int n,m,a,b,c,cnt[N],sum,num[N];
bool check(int x){
    rep(i,1,m) if(cnt[i]<x) return 0;
    int res=0;
    rep(i,1,m) res+=min(num[i],cnt[i]-x);
    return res>=x;
}
signed main(){
    read(n,m);
    rep(i,1,n){
        read(a,b,c);
        if(c) num[a]++;
        sum+=b;
        cnt[a]+=b;
    }
    int l=0,r=sum;
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid)) l=mid+1;
        else r=mid-1;
    }
    cout<<l-1;
    return 0;
}