百度笔试题组队

题目描述

有n个人，每个人的能力值为\(a_i\)，性格值为\(b_i\)，要将这n个人分成若干组，每个人只能在一个组内。我们定义两个人的差别值为\(|a_i-a_j|+|b_i-b_j|\).
规定一个差别上限L，如果两个人的差别值不超过L，那么在分组结果中这两人一定会在同一份组内（当然，即使两个人差别值超过L，两个人还是可以在同一小组，只是不超过L的必须在一组）。
现在我们想知道，如果能将所有人分成至少K个非空的小组，规定的差別上限最多为多少。

输入描述

第一行两个正整数n,k，表示人数和分组要求。
接下来两行每行n个整数，表示\(a_1,a_2,...a_n; b_1,b_2,...b_n\)

输出描述

输出一个整数表示最大的差别上限

样例输入

3 2
1 9 3
2 7 8

样例输出

思路

首先将问题简化，我们将每个人表示为一个图中的节点，两个人之间的差别值用节点间边的权重表示，这个图是一个完全图。如何找出差別上限的最大值呢？

我们可以在构建图的时候，记录下权重的最大值和最小值，符合条件的差别上限的最大值一定在这个范围之间。最简单的方法，我们可以从小到大一个一个试这些差别上限。

对于某个差别上限L，对图中的每个节点为起点，分别开始dfs搜索，在搜索的过程中，如果达到邻居节点的权重小于等于差别上限L，那么这个节点可达。搜索结束，计算出可以分组的个数，也就是连通分量。

如果某次差别上限为L，计算出的分组数小于分组要求k，那么最大的差别上限就是L-1。但是这样做时间复杂度太高，可以用二分查找优化。二分查找

代码

def dfs(x, d_):
    if visited[x]:
        return

    visited[x] = True

    for i in range(n):
        if i == x:
            continue
        if graph[x][i] <= d_:
            dfs(i, d_)


n, k = map(int, input().split())
a_i = [int(i) for i in input().split()]
b_i = [int(i) for i in input().split()]

# 使用邻接矩阵记录图
graph = [[0] * n for i in range(n)]
max_d, min_d = -float('inf'), float('inf')

for i in range(n):
    for j in range(n):
        if i == j:
            continue
        d = abs(a_i[i] - a_i[j]) + abs(b_i[i] - b_i[j])
        graph[i][j] = d
        graph[j][i] = d
        if d > max_d:
            max_d = d
        if d < min_d:
            min_d = d

# 利用二分查找找出最大的差别上限
l, r = min_d - 1, max_d + 1
while l + 1 != r:
    m = (l + r) // 2

    # 计算可以分组的数量
    visited = [False] * n
    connect_num = 0
    for i in range(n):
        if visited[i]:
            continue
        dfs(i, m)
        connect_num += 1

    if connect_num < k:
        r = m
    else:
        l = m

print(l)