题解：P14575 坤班

题目链接

https://www.luogu.com.cn/problem/P14575

分析

让愿意当班主任的老师全部当班主任，记班主任数量为

hcnt

。同时对于每门学科，记录能教的班级数量和该学科老师中的班主任数量，分别记为

tcnt_{i, 1}, tcnt_{i, 2}

。

答案应为班主任数量和最小学科容量中的较小值。

由于可能不需要所有愿意当班主任的老师都当班主任，可以每次找出

tcnt_{i, 1}

最小的学科，若

tcnt_{i, 2} > 0

，则令

tcnt_{i, 1} \longleftarrow tcnt_{i, 1} + 1, tcnt_{i, 2} \longleftarrow tcnt_{i, 2} - 1, hcnt \longleftarrow hcnt - 1

，即将该学科中一位愿意当班主任的老师置为非班主任以增加学科容量。每次操作后更新答案即可。

细节内容见代码注释。

Code

CPP

#include <bits/stdc++.h>

#define int long long

using namespace std;

constexpr int N = 5e5 + 5;
int n, m, a[N][5], hcnt;
pair<int, int> tcnt[N];

// 堆顶学科容量最小 
struct comp
{
	bool operator () (const pair<int, int> &pr1, const pair<int, int> &pr2) const
	{
		return pr1.first > pr2.first;
	}
};
priority_queue<pair<int, int>, vector<pair<int, int> >, comp> hp;

signed main()
{
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	
	cin >> n >> m;
	
	for (int i = 1; i <= n; ++ i)
	{
		cin >> a[i][1] >> a[i][2] >> a[i][3];
		
		// 置为班主任 
		if (a[i][3] == 1)
		{
			++ hcnt, ++ tcnt[a[i][1]].second;
			-- a[i][2];
		}
		// 更新学科容量 
		tcnt[a[i][1]].first += a[i][2];
	}
	
	for (int i = 1; i <= m; ++ i)
	{
		hp.push(tcnt[i]);
	}
	
	int ans = 0;
	for (; !hp.empty();)
	{
		pair<int, int> frt = hp.top();
		hp.pop();
		
		// 更新答案 
		ans = max(ans, min(hcnt, frt.first));
		// 容量最小的学科没有挽回空间，直接 break 
		if (frt.second == 0 || hcnt < frt.first)
		{
			break;
		}
		
		// 将本学科中一位班主任置为非班主任 
		++ frt.first, -- frt.second, -- hcnt;
		hp.push(frt);
	}
	
	cout << ans << endl;
	return 0;
}

文章操作

题目链接

分析

Code

相关推荐

评论

题解：P14575 坤班