P14575 题解

Aurora_Lights · 2025-11-23 19:38:12 · 题解

显然如果较多的班级数目合法那么较少的一定也合法，故考虑二分答案。判定时先考虑每个学科在满足需求之后多出来能教多少个班（优先排非班主任，那么多出来的班数和班主任数目取较小值即为可以安排的班主任数量），最后再看总共能安排的班主任数量是否足够即可。时间复杂度 O(m\log V)。

#include<iostream>
#include<cstdio>
#define int long long
#define N 1000010
using namespace std;
int n,m,a[N],b[N];
bool ck(int x){
    int cnt=0;
    for(int i=1;i<=m;i++){
        if(a[i]<x)return false;
        cnt+=min(b[i],a[i]-x);
    }
    return cnt>=x;
}
signed main(){
    int x,y,z;
    cin>>n>>m;
    while(n--){
        cin>>x>>y>>z;
        a[x]+=y,b[x]+=z;
    }
    int l=0,r=1e10,mid,ans=0;
    while(l<=r){
        mid=(l+r)/2;
        if(ck(mid))ans=mid,l=mid+1;
        else r=mid-1;
    }
    cout<<ans;
    return 0;
}