P14575 坤班 题解

· · 题解

1. 题意解释

我懒，自己看题干去吧。

2. 思路

不难发现答案具有单调性，考虑二分答案。

考虑对于某个答案 x 如何判断其合法性。

我们预处理出对于某种学科 i，在不考虑班主任的情况下总共最多可以教多少个班，记为 sum_i。

然后我们考虑每个老师 i，若 sum_{a_i}>x，则他当班主任后依然可以使得 x 个班级的教学需求得到满足，就让他去当班主任，然后 sum_{a_i} 减一。

可以发现这样的策略一定是不劣的，于是就做完了。

3. 代码实现

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[500500],b[500500],c[500500],sum[500500],tmp[500500],minn=1e18,cnt,ans;
bool check(int x){
    int res=0;
    for(int i=1;i<=m;i++){
        tmp[i]=sum[i];
    }
    for(int i=1;i<=n;i++){
        if(tmp[a[i]]>x&&b[i]>=1&&c[i]==1){
            res++;
            tmp[a[i]]--;
        }
    }
    if(res>=x){
        return true;
    }
    return false;
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i]>>b[i]>>c[i];
        sum[a[i]]+=b[i];
        cnt+=c[i];
    }
    for(int i=1;i<=m;i++){
        minn=min(minn,sum[i]);
    }
    minn=min(minn,cnt);
    int l=0,r=minn;
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid)){
            ans=mid;
            l=mid+1;
        }
        else{
            r=mid-1;
        }
    }
    cout<<ans;
    return 0;
}