C++: 发工资的快乐值 - 二分搜索解题思路

解题思路\n\n根据题意，我们需要找到一个最小的整数 $k$，使得所有员工的快乐值都不低于他们的期望快乐值。\n\n我们可以通过二分搜索来找到满足条件的最小 $k$ 值。\n\n首先，我们需要确定二分搜索的上下界。\n\n由于快乐值是非负的，所以对于任意的 $k$，员工的快乐值都不会小于 $k$。\n\n而对于任意的 $k' > k$，员工的快乐值都不会小于 $k'$。\n\n所以，我们可以将二分搜索的下界设置为 $0$，上界设置为员工的期望快乐值的最大值。\n\n然后，我们需要确定二分搜索的判定条件。\n\n对于给定的 $k$ 值，我们可以按照以下方式计算员工的快乐值：\n\n- 首先，将所有员工的快乐值初始化为 $0$。\n- 对于每个获得工资的员工 $b_i$，将其快乐值增加 $k$。\n- 对于每个员工 $a_j$，计算其与获得工资的员工之间的距离 $d$，如果 $d \leq k$，则将其快乐值增加 $k-d$。\n\n如果所有员工的快乐值都不低于他们的期望快乐值，那么说明当前的 $k$ 值是满足条件的。\n\n我们可以使用一个辅助数组 happiness 来保存每个员工的快乐值。\n\n现在，我们可以开始二分搜索了。\n\n我们将二分搜索的下界设置为 $0$，上界设置为员工的期望快乐值的最大值。\n\n在每一次二分搜索的过程中，我们计算出当前的 $mid$ 值，并计算员工的快乐值。\n\n然后，我们检查员工的快乐值是否都不低于他们的期望快乐值。\n\n- 如果是，说明我们可以将 $k$ 值设置为更小的值，我们将上界更新为 mid，并继续二分搜索。\n- 如果不是，说明我们需要将 $k$ 值设置为更大的值，我们将下界更新为 mid + 1，并继续二分搜索。\n\n当下界和上界相等时，我们找到了最小的满足条件的 $k$ 值。\n\n最后，我们输出这个 $k$ 值即可。\n\n算法描述\n\n1. 读入输入的数据，并初始化二分搜索的下界 low 为 $0$，上界 high 为员工的期望快乐值的最大值。\n2. 当 low 小于 high 时，执行以下步骤：\n - 将 mid 设置为 low 和 high 的中间值。\n - 初始化员工的快乐值数组 happiness 为全 $0$。\n - 对于每个获得工资的员工 $b_i$，将其快乐值增加 mid。\n - 对于每个员工 $a_j$，计算其与获得工资的员工之间的距离 $d$，如果 $d \leq mid$，则将其快乐值增加 mid - d。\n - 检查员工的快乐值是否都不低于他们的期望快乐值，如果是，将上界 high 更新为 mid，否则将下界 low 更新为 mid + 1。\n3. 输出结果 low。\n\n复杂度分析\n\n- 时间复杂度：二分搜索的时间复杂度为 $O(\log(\max(\text{期望快乐值})))$。\n- 空间复杂度：$O(n)$，需要使用一个辅助数组来保存员工的快乐值。