解题思路
这道题目要求从每个战队中选择一名成员,组成一个队伍,使得所选成员的战力极差(即最大战力与最小战力之差)最小。为了实现这一点,我们首先读取每个战队成员的战力值,并将每个成员的战力与所属的战队编号一起存储。接着,我们将所有战队成员的战力值按升序排序,这样排序后的战力值便于我们快速选择最小的战力差。然后,我们使用滑动窗口技术来查找最小的战力极差。滑动窗口的左右边界分别为 left 和 right,通过移动这些边界,我们可以确保每个战队的成员都被包含在窗口内。为了记录当前窗口覆盖的队伍,我们使用一个 defaultdict 来记录每个战队的成员数,同时维护一个 covered_teams 变量,表示当前窗口覆盖的战队数。当窗口包含了所有战队时,我们计算当前窗口的最大战力和最小战力之差,并更新最小的战力极差。每次收缩窗口时,都会更新当前窗口的战力极差,并与之前的最小极差进行比较,最终输出最小的战力极差。通过这种方式,我们能在较短的时间内找到最平衡的队伍配置。
代码