P14575 坤班

发表于 更新于

P14575 坤班

题目描述

传奇颜值中学开始招生了！

学校里面有 $n$ 个老师，需要教授 $m$ 个学科。每一个老师可以用一个三元组 $(a_i,b_i,c_i)$ 表示其教 $a_i$ 这个学科，最多能教 $b_i$ 个班级。若 $c_i = 0$ 表示老师 $i$ 不愿意当班主任，反之表示其愿意当班主任。

特别的，因为担任班主任将会消耗大量的精力，所以如果一个老师 $i$ 选择担任班主任，他就最多只能教授 $b_i - 1$ 个班级。

当然，每一个班必须有一个班主任，每一个学科必须有一名老师教授。需要注意的是一个班主任并不必须担任他所对应班级的科任老师。

学校希望能组建更多的班级，以招到更多优秀的 OIer，招生组特邀作为传奇特级大师的你来协助计算出能够组建出最多的班级数量。

输入格式

第一行读入两个正整数 $n,m$，分别表示传奇颜值中学中老师的数量和学科的数量。

接下来 $n$，每行包含三个整数 $a_i,b_i,c_i$，其含义见题目描述。

输出格式

输出共一行，表示传奇颜值中学能组建出最多的班级数量。

输入输出样例 #1

输入 #1

1
2
3
4
5
6
5 2
1 2 1
1 2 1
1 1 0
2 2 1
2 2 1

输出 #1

1
3

说明/提示

样例解释

编号为 $1,2,4$ 的老师分别担任三个班的班主任。

编号为 $1,2,3$ 的老师分别教授三个班的学科 1。

编号为 $4$ 的老师教授一个班的学科 2，编号为 $5$ 的老师教授两个班的学科 2。

数据范围

子任务 $n \leq $ 特殊性质 分值
Subtask 1 $5 \times 10^5$ A $5$
Subtask 2 $20$ 无 $15$
Subtask 3 $3 \times 10^3$ B $20$
Subtask 4 $3 \times 10^3$ 无 $20$
Subtask 5 $5 \times 10^5$ B $20$
Subtask 6 $5 \times 10^5$ 无 $20$
  • 特殊性质 A：满足 $\forall i \in [1,n],c_i = 0$。
  • 特殊性质 B：满足 $\forall i \in [1,n],b_i = 1$。

对于 $100\%$ 的数据满足：

  • $m \leq n$。
  • $\forall i \in [1,n]$，$1 \leq a_i \leq m$，$1 \leq b_i \leq n$，$c_i \in {0,1}$。

思路分析 + 代码实现

一开始的想法：我们要想组建出尽可能多的班级，肯定要贪心一点。具体怎么贪心呢？首先，对于不愿意当班主任的老师，我们自然是狠狠压榨让他们多干活，即安排满ta的教学班级。愿意当班主任的老师呢，自然是比较珍贵，不能随意安排，要好好考虑。

但是，分析到这里，我们发现还是很难直接判断出能组建出多少班级。换个思路，判断能否组建出 $k$ 个班级相对容易一些。具体怎么判断呢？

用数组 $head$ 记录每个学科班主任的数量，用数组 $subject$ 记录每个学科的教学能力（含班主任）。对每个 $k$ 先让所有老师都不当班主任，狠狠上课。如果这样都有学科凑不够老师，那么说明肯定组不出 $k$ 个班。如果凑得出，那么就要考虑班主任，用变量 $cnt$ 记录可用的班主任数量，对每个学科来说，多出 $subject[i] - mid$ 个老师，如果 $head[i]$ 足够（不小于这个数）就分配 $subject[i] - mid$ 个班主任，否则只能分 $head[i]$ 个。最后检查班主任够不够 $k$ 个即可。

再加上这道题答案具有“单调性”，因此我们采取二分答案的做法，找出满足条件的最大的 $k$ 即为答案，时间复杂度为 $O(n\operatorname{log}(n_{max}))$ ，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
constexpr LL MAXN = 5e5 + 2;
// 刚做这道题目只想到模拟，超时了，写个快读玩玩 QWQ
LL read() { 
    LL ch = getchar(), result = 0;
    while (!(ch >= '0' && ch <= '9')) 
        ch = getchar();
    while (ch >= '0' && ch <= '9') {
        result = result * 10 + (ch - '0');
        ch = getchar();
    }
    return result;
}
LL head[MAXN]; // 每个学科班主任的数量
LL subject[MAXN]; // 每个学科的教学能力（含班主任）
int main() {
    LL n, m, a, b, c, ans = 0;
    n = read(); m = read();
    for(LL i = 0; i < n; i++) {
        a = read(); b = read(); c = read();
        if (c) head[a]++;
        subject[a] += b;
    }
    LL l = 0, r = MAXN * MAXN;
    while (l <= r) {
        LL mid = (l + r) / 2;
        LL cnt = 0; // 计算可用班主任的数量
        bool valid = true;
        for(int i = 1; i <= m; i++) { // 遍历学科
            if (subject[i] < mid) { // 老师不够
                valid = false;
                break;
            }
            cnt += min(subject[i] - mid, head[i]);
        }
        if (cnt < mid) // 班主任不够
            valid = false;
        if (valid) {
            ans = mid;
            l = mid + 1;
        }
        else r = mid - 1;   
    }
    cout << ans;
    return 0;
}