题解：P14575 坤班

· · 题解

思路

题目要求我们求出能组建出最多的班级数量。

一看到最多的班级数量，我们不难想到这道题可以用二分班级数量来做。因为如果 x 个班级可以组建，那么 x-1 个班级也一定可以组建，但是如果 x 个班级不能组建，那么 x-1 个班级也一定不能组建。

那么现在的问题就是如何判断能否组建这么多的班级数量。

我们发现，一共存在两种情况使得我们无法组建这么多的班级数量：

  1. 一个学科的所有老师能教的班级数比要组建的班级数要少；
  2. 班主任的数量比要组建的班级数要少。

按照贪心策略，我们肯定要在所有班级都有这科的老师教的情况下，让这科有空的老师尽量去当班主任。因为即使这些老师当了班主任，也不会影响这些班都有这科老师教。

那么我们可以计算一下在所有班级都有这科的老师教的情况下，都有多少有空的老师愿意当班主任。这里有两种情况：

  1. 当这科老师剩余可教班级数减去这科想要当班主任的老师数大于等于班级数时，我们肯定让想当班主任的老师全都当班主任。
  2. 当这科老师剩余可教班级数减去这科想要当班主任的老师数小于班级数时，让剩下多于班级数的这科老师去当班主任最好。

说的可能有些抽象，下面我来用一张图解释：

其中蓝线为 x 个班级，黑色线段表示学科老师能教的班级总数数，绿框表示一科中愿意去当班主任的老师数，红色部分即为要去当班主任的老师，而黄色部分由于要当任课老师，所以无法成为班主任。

图中第一个学科即为第一种情况，第二个学科即为第二种情况。

据此，我们遍历每一个学科并比较这科师能教的班级数和要组建的班级数，最后把班主任数和班级数比较一下即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
void st(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
const int nm=5e5+10;
int n,m,k,ans;
int a[nm],b[nm],c[nm];
int sub[nm],num[nm];
bool ok(int x){
    int sum=0;
    for(int i=1;i<=m;i++){
        if(sub[i]<x) return 0;
        if(sub[i]-num[i]>x) sum+=num[i];
        else sum+=sub[i]-x;
    }
    if(sum<x) return 0;
    return 1;
}
signed main(){
    st();
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i]>>b[i]>>c[i];
    for(int i=1;i<=n;i++){
        sub[a[i]]+=b[i];
        num[a[i]]+=c[i];
    }
    int l=0,r=n;
    while(l<=r){
        int mid=(l+r)>>1;
        if(ok(mid)) ans=mid,l=mid+1;
        else r=mid-1;
    }
    cout<<ans;
    return 0;
}