1250L - Divide The Students（源地址自⇔CF1250L）

• 1250L - Divide The Students（源地址自⇔CF1250L）
  • Problem
  • tag
  • 题意
  • 思路
  • AC代码（数论，伪代码）
  • 错误次数

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 成文