题解：P14575 坤班

Ljh421 · 2025-11-23 18:56:59 · 题解

比较容易发现的二分题（还想还是贪心）。

Idea

首先是不愿意当班主任的老师，肯定能教 b_i 个班级，不需要考虑太多。

不考虑这个老师愿意当班主任这件事，先把他当作普通老师，可以得到每个科目的老师一共可以教多少个班级，放到数组 sum 中。

可以发现最终答案的可能最大值为数组 sum 的最小值，可能最小值为 0。

然后我们可以二分答案了，但怎么检查答案是否合法呢？

设 mid 为当前检查的答案，sum_i 为教第 i 个科目最多可教多少个班。那么可以减少教 sum_i - mid 个班，也就是教这个科目的老师最多可以有 sum_i - mid 个班主任。

然而可能教这个科目的老师没有 sum_i - mid 个愿意当班主任，所以要取最小值。

但这里思路就没了。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+10;
int n,m,ans,ai;
int sum[N];
int ban[N],q[N];
int minn=N;
int l,r,mid;
bool check(int mid){
    int k=0;
    for(int i=1;i<=m;i++){
        k+=min(ban[i],sum[i]-mid);
    }
    if(k>=mid) return 1;
    return 0;
}
signed main(){

    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);

    cin>>n>>m;
    for(int i=1,x,y,z;i<=n;i++){
        cin>>x>>y>>z;
        if(!z){
            sum[x]+=y;
        }else{
            ban[x]++;
            sum[x]+=y;
        }
    }
    for(int i=1;i<=m;i++){
        q[i]=sum[i]+q[i-1];
        minn=min(minn,sum[i]);
    }
    r=minn;
    while(l<=r){
        mid=(l+r)>>1;
        if(check(mid)){
            l=mid+1;
            ans=mid;
        }else{
            r=mid-1;
        }
    }
    cout<<ans;

    return 0;
}