1250L - Divide The Students(贪心+数学/二分搜索法/提高级)

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

目录

Problem

1250L - Divide The Students(贪心+数学/二分搜索法/提高级)

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


上一篇:IfcArithmeticOperatorEnum


下一篇:C - Divide and Multiply