- 「基础数据结构2」树和堆
建筑抢修(反悔贪心)
- @ 2025-10-27 22:51:14
大致思路: 将所有建筑的限制时间升序排序,确保当前处理的建筑的限制时间一定大于计划要抢修的建筑。 将计划要抢修的建筑的时间排入优先队列(最大堆,即时间最大的在最顶上) 接下来分情况讨论: 1.当前建筑抢修需要的时间加上已计划抢修的建筑所需时间的总和不超过当前建筑的限制时间,则可以直接入队。 2.否则如果当前建筑的抢修需要的时间比计划抢修的建筑的最大时间要小,则替换最顶上的建筑,转而修当前建筑(限制时间是肯定不会超过的,因为限制时间升序排列已经保证这一点)。 为了防止cv,这边只给出部分代码
while (!pq.empty() && i<n) {
auto p = pq.top();
if (sum+v[i].time <=v[i].limit && i<n) {//当前建筑的时间加上计划修复的建筑的总时间之和小于当前建筑的限制时间
pq.push(v[i].time);
sum+=v[i].time;
}
else if (p >= v[i].time &&i<n) {//当前建筑修复需要的时间小于计划修复的建筑的最大时间
sum-=p;
pq.pop();
pq.push(v[i].time);
sum+=v[i].time;
}
i++;
}
```
0 条评论
目前还没有评论...