[BZOJ1029][JSOI2007]建筑抢修

n件任务需要完成。第i个任务需要t_i的时间完成,deadline是d_i。每个任务必须在连续的一段时间内被完成,问最多能有多少任务按时完成。

链接

BZOJ 1029

题解

这好像是本质不同的一种贪心方法呀qwq

做某个任务的时间需要连续这个限制是没有用的:假设某些任务在间断的时间内被完成。我们可以按照任务被完成的顺序来连续地解决这些问题,这样每个问题被完成的时间不会变晚。

我们可以反转时间轴:时间从T流逝到0,从t_i时间开始可以做i号任务,求最多能做多少任务,显然每次只需要做剩下的任务中耗时最小的就行了。

在时间从T流逝到0的过程中,可能会影响当前做的任务的事件只有两种:

  1. 完成了某个任务
  2. 得到了某个新任务

每种事件的出现次数都不超过n,因此只要用一个堆维护任务还需要多长时间做完,时间复杂度为O(n\log n)

代码
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int Siz = 2e5;

priority_queue<int, vector<int>, greater<int> > pq;

int n, t, ans;
pii item[Siz];

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d%d", &item[i].second, &item[i].first);
    sort(item + 1, item + n + 1); t = item[n].first;
    for(int i = n; ~i; i--) {
        while(!pq.empty()) {
            int cur = pq.top(); pq.pop();
            if(t - item[i].first >= cur) {
                t -= cur; ans++;
            } else {
                cur -= t - item[i].first; t = item[i].first;
                pq.push(cur);
                break;
            }
        }
        pq.push(item[i].second); t = min(t, item[i].first);
    }
    printf("%d\n", ans);
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注