题解：P14575 坤班

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

Idea

首先是不愿意当班主任的老师，肯定能教

b_i

个班级，不需要考虑太多。

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

sum

中。

可以发现最终答案的可能最大值为数组

sum

的最小值，可能最小值为

0

。

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

设

mid

为当前检查的答案，

sum_i

为教第

i

个科目最多可教多少个班。那么可以减少教

sum_i - mid

个班，也就是教这个科目的老师最多可以有

sum_i - mid

个班主任。

然而可能教这个科目的老师没有

sum_i - mid

个愿意当班主任，所以要取最小值。

但这里思路就没了。

Code

CPP

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

文章操作

Idea

Code

相关推荐

评论

题解：P14575 坤班