P7585 LJUBOMORA 题解

chlchl · 2021-05-29 20:39:51 · 题解

题目及意思

题目传送门。

这道题若难以理解“嫉妒值”的意思，先别急着看题解，可以结合样例来帮助理解题目的意思。这里就先拿题目的样例来做例子分析。

有 4 个红色的弹珠和 7 个蓝色的弹珠，要分给 5 个孩子，那么我们可以这样划分（红为 R，蓝为 B）：\texttt{RR},\texttt{RR},\texttt{BB},\texttt{BB},\texttt{BBB}。这样分的嫉妒值为 3，是最小的。

看出来了吧？这题其实是让我们找到一种合适的方案，分给每个人之后让他们之中的最大值最小。

思路

这道题正解是二分，关键词为最大值（即嫉妒值）最小。看到这种问题的可优先考虑二分。确定核心算法后，进一步分析发现：如果每个分到弹珠的孩子都分到最多的弹珠，那么嫉妒值越大，分到弹珠的孩子越少；嫉妒值越小，分到弹珠的孩子越少。这个嫉妒值是具有单调性的，满足二分的要求。所以确定本题为二分答案。

以下为二分模板。

while(l <= r){
        mid = (l + r) / 2;
        if(check(mid)){//check 函数需要手写
            r = mid - 1;//不同题目可能这里不太一样
        }else   l = mid + 1;//同上
    }
}

若连上面的模板都不能打出来的话建议先去做一下P2249。

check函数的思路：我们需要将相同颜色的弹珠尽量按当前枚举的数量平均分给小盆友们，具体的模拟过程就是除法。我们通过二分枚举嫉妒值 mid，发现第 i 种颜色的弹珠数 a_i 至少需要分给 \left\lceil\dfrac{a_i}{mid}\right\rceil 个孩子。最后把每种颜色的弹珠所分得的孩子数加起来就得到最小的孩子数了。

一些小坑

1. 二分答案时，不能将 mid 直接当做答案输出，要将它的值赋给 ans，输出 ans，否则你会只有 90 分。

2. 注意二分条件和范围。

3. check 函数求每种颜色的弹珠可分得的人数时，应注意判断是否整除，如出现余数则人数应该+1，因为是向上取整.

4. 谨记：五年 OI 一场空，不开 long long 见祖宗！ 不开 long long 会 WA 两个点，只有 90 分。

代码

要什么代码，自己写嘛。

以下是参考代码，我真诚地劝大家不要抄袭。