P14575 坤班题解

1. 题意解释

~~我懒，自己看题干去吧。~~

2. 思路

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

考虑对于某个答案

x

如何判断其合法性。

我们预处理出对于某种学科

i

，在不考虑班主任的情况下总共最多可以教多少个班，记为

sum_i

。

然后我们考虑每个老师

i

，若

sum_{a_i}>x

，则他当班主任后依然可以使得

x

个班级的教学需求得到满足，就让他去当班主任，然后

sum_{a_i}

减一。

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

3. 代码实现

CPP

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

文章操作

1. 题意解释

2. 思路

3. 代码实现

相关推荐

评论

P14575 坤班题解