题解：P14575 坤班

考虑二分班级数量，设二分到的答案为

x

，则需要满足两个条件：

当班主任的人数 $\ge x$ 。
设 $f_i$ 表示学科 $i$ 能教到 $f_i$ 个班级，则 $\min_{i=1}^nf_i\ge x$ 。

设

num_i

表示教学科

i

的老师有多少愿意当班主任，则对于每个学科，已知二分班级

x

，可以得到这个学科最多能有

\min(num_i,f_i-x)

个老师当班主任。

代码

CPP

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;
}

文章操作

代码

相关推荐

评论

题解：P14575 坤班