1 条题解

  • 0
    @ 2026-11-15 14:10:19

    题目分析

    30 pts

    对于 30%30\% 的数据,n≤5n \le 5,k≤2k \le 2。

    当 k=1k = 1 时,显然答案为 00。

    当 k=2k = 2 时,暴力枚举两个点,求出距离即可。 时间复杂度 O(n2)O(n^2)。

    60 pts

    因为坐标范围不大,因此可以枚举所有可能的 P。

    将所有点到 P 的距离从小到大排序,即可求出每个 t 的答案。

    时间复杂度 O(x2nlog⁡n)O(x^2n \log n)。

    100 pts

    假设已知选取了哪 tt 个点,则 PP 显然取两维的中位数时最优。

    这意味着 PP 的横纵坐标一定从给定的 nn 个点的横纵坐标中 选取。

    在此基础上枚举所有 PP 即可。

    时间复杂度 O(n3log⁡n)O(n^3 \log n)。

    • 1

    信息

    ID
    90
    时间
    1000ms
    内存
    256MiB
    难度
    5
    标签
    递交数
    1
    已通过
    1
    上传者