1 条题解
-
0
题目分析
贪心 + 排序。
每位大臣能接受的工资是一个区间 :金砖价值必须不低于 (工资),且不能超过 (上限)。每块金砖价值固定,每位大臣至多分到一块金砖,目标是让尽量多的大臣满意。
这是一个经典的「区间贪心匹配」问题:
- 把金砖按价值升序排序;
- 把大臣按其可接受区间的右端点 升序排序;
- 依次处理每位大臣,在所有尚未使用的金砖中,选择价值最小的、且落在 内的那块分给他;若不存在这样的金砖,则该大臣无法被满足(或者等价地,跳过)。
这里用「按右端点升序」排序是关键:越早结束的区间越应该优先满足,否则那块金砖可能被后面区间更宽的大臣占用,导致最优解变差。具体实现可以用一个有序容器(如
multiset)维护尚未使用的金砖价值,二分查找首个 的位置,并检查是否 。总时间复杂度 。
- 1
信息
- ID
- 115
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 4
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者