信息
- ID
- 90
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 5
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者
对于 30% 的数据,n≤5,k≤2。
当 k=1 时,显然答案为 0。
当 k=2 时,暴力枚举两个点,求出距离即可。 时间复杂度 O(n2)。
因为坐标范围不大,因此可以枚举所有可能的 P。
将所有点到 P 的距离从小到大排序,即可求出每个 t 的答案。
时间复杂度 O(x2nlogn)。
假设已知选取了哪 t 个点,则 P 显然取两维的中位数时最优。
这意味着 P 的横纵坐标一定从给定的 n 个点的横纵坐标中 选取。
在此基础上枚举所有 P 即可。
时间复杂度 O(n3logn)。