1 条题解

  • 0
    @ 2026-11-15 15:17:21

    题目分析

    贪心 + 排序。

    每位大臣能接受的工资是一个区间 [Li,Ri][L_i, R_i]:金砖价值必须不低于 LiL_i(工资),且不能超过 RiR_i(上限)。每块金砖价值固定,每位大臣至多分到一块金砖,目标是让尽量多的大臣满意。

    这是一个经典的「区间贪心匹配」问题:

    1. 把金砖按价值升序排序;
    2. 把大臣按其可接受区间的右端点 RiR_i 升序排序;
    3. 依次处理每位大臣,在所有尚未使用的金砖中,选择价值最小的、且落在 [Li,Ri][L_i, R_i] 内的那块分给他;若不存在这样的金砖,则该大臣无法被满足(或者等价地,跳过)。

    这里用「按右端点升序」排序是关键:越早结束的区间越应该优先满足,否则那块金砖可能被后面区间更宽的大臣占用,导致最优解变差。具体实现可以用一个有序容器(如 multiset)维护尚未使用的金砖价值,二分查找首个 ≥Li\ge L_i 的位置,并检查是否 ≤Ri\le R_i。

    总时间复杂度 O((n+m)log⁡m)O((n+m)\log m)。

    • 1

    信息

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