1 条题解

  • 0
    @ 2025-11-18 16:03:55

    这是一道典型的贪心匹配题。

    将韩国选手的线段和中国选手的点按坐标从小到大排序,用两个指针逐一扫描。

    • 若当前点落在当前线段范围内,则配对成功,答案加一,同时两个指针都向右移动;
    • 否则移动左端更小的一方指针,使其尽量赶上另一方。 贪心正确性的关键在于最小点优先匹配最靠左的可行线段这一原则:
    • 若最优解中最小的点未被匹配,则我们将它与最靠左能容纳它的线段匹配,不会影响其他匹配;
    • 若最优解中该点匹配了更右的线段,而更左线段也能容纳它,则将匹配替换为更左线段后整体方案仍不劣。

    因此此策略必定最优。

    时间复杂度:o(nlogn)o(nlogn)

    • 1

    信息

    ID
    4
    时间
    1000ms
    内存
    256MiB
    难度
    4
    标签
    递交数
    37
    已通过
    6
    上传者