思路概述

把每个人看作图的一个点，若两人差别值 $|a_i-a_j|+|b_i-b_j|\le L$，就在两点之间连一条“必须同组”的边。这样图的每个连通块中的人都被强制在同一组里；而不同连通块之间可以自由合并或各自成组。

于是，当给定 $L$ 时，“至少能分成多少组”的下界正是该图的连通块个数 $cc(L)$。题目等价于：求最大的整数 $L$，使得 $cc(L)\ge k$。

注意 $L$ 增大只会增加边数、使连通块数不增反减，因此性质单调：若某个 $L$ 可行（$cc(L)\ge k$），则任意更小的 $L$ 也可行。于是可二分答案。

算法与实现

题目内容

小红的公司要进行集体活动，活动要求所有人员分组。

当前有 $n$ 个人，每个人的能力值为 $a_i$ ，性格值为 $b_i$，现在希望将这 $n$ 个人分成若干组，每个人只能在一个组内。

当然，分组是一个问题，我们定义两个人的“差别值”为能力值的差和性格值的差的绝对值之和，即 $|a_i-a_j|+|b_i-b_j|$。