1250L - Divide The Students（源地址自⇔CF1250L）
目录Problem
tag
⇔贪心、⇔数学、⇔二分搜索法、⇔提高级（*1500）
题意
（简化版）
\(A, B, C\) 三群人，人数分别为 \(a, b, c\) ，按要求分成三个班，使得人数最多的那个班的人数最少，要求如下：
- \(a\) 群人和 \(c\) 群人不能分到同一个班。
思路
（队内赛自己，数论）
未严格证明，但是正式赛的时候好多队伍都是这么做的，显然是最优解。
不妨设 \(a \le c\) ，那么显然， \(A\) 人至多分为一个班， \(C\) 人至多分为两个班。
- 当 \((a + b) < \left \lceil \frac{c}{2} \right \rceil\) 时，即 \(A, B\) 人分到一个班级， \(C\) 人分成两个班级，答案为 \(\left \lceil \frac{c}{2} \right \rceil\) 。
- 其他情况，先计算出无要求时的分班情况，即 \(\left \lceil \frac{a + b + c}{3} \right \rceil\) ，再判断其与 \(a\) 的关系（ \(A\) 人不可以分割成两个班），答案为 \(max( \left \lceil \frac{a + b + c}{3} \right \rceil, a)\) ，即是否是 \(A\) 人单独一个班级， \(B, C\) 人分成两个班级。
（网络大佬做法，二分搜索法）
这个方法比较好理解，且很显然，不用证明，但是代码难度上升。
先考虑只有 \(A, C\) 人的情况，不妨设 \(a \le c\) ，那么显然， \(A\) 人至多分为一个班， \(C\) 人至多分为两个班。将 \(C\) 人平分为两个班，现在三个班的人数分别是：\(a, c - \frac{c}{2}, \frac{c}{2}\) 。
再考虑 \(B\) 人，灵活分配到三个班中，使得人数最多的那个班的人数最少。
AC代码（数论，伪代码）
cin >> a >> b >> c;
if(a > c) swap(a, c);
if(a + b < (c + 1) / 2)
cout << (c + 1) / 2 << endl;
else {
numx = (a + b + c + 2) / 3;
cout << max(numx, a) << endl;
}
错误次数
（队内赛1）未考虑 \(a,c\) 的大小，WA。
文 / WIDA
2021.12.20 成文
首发于WIDA个人博客，仅供学习讨论
更新日记：
2021.12.20 成文