BZOJ 1029 - [JSOI2007]建筑抢修

Published on 2016-08-26

题目地址

描述

小刚在玩 JSOI 提供的一个称之为“建筑抢修”的电脑游戏:经过了一场激烈的战斗,T 部落消灭了所有 z 部落的入侵者。但是 T 部落的基地里已经有 n(n150000)n(n\le 150000) 个建筑设施受到了严重的损伤,如果不尽快修复的话,这些建筑设施将会完全毁坏。现在的情况是:T 部落基地里只有一个修理工人,虽然他能瞬间到达任何一个建筑,但是修复每个建筑都需要时间 t1t_1。同时,修理工人修理完一个建筑才能修理下一个建筑,不能同时修理多个建筑。如果某个建筑在 t2t_2 之前没有完全修理完毕,这个建筑就报废了。你的任务是帮小刚合理制订一个修理顺序,以抢修尽可能多的建筑。

分析

贪心题,我尝试证明一下。能力有限,证错了请指正

方法:按照 t2t_2 从小到大排序,顺序放置区间,如果当前区间 ii 可以放,那么就放,否则替换掉已经放下的满足 t1(j)>t1(i)t_1(j) > t_1(i)t1(j)t_1(j) 最大的一个区间(不存在则放弃该区间)。

命题一:存在一个没有间隙的最优解。
证明:若在某最优解中,两相邻区间 i,i+1i, i + 1 之间有空闲段,可将 i+1,i+2,i + 1, i + 2, \cdots 全部往左移,直至 i,i+1i, i + 1 之间没有空闲段。显然答案只增不减。

命题二:上述算法构造出的是最优解(放置区间最多,右端点最左)。
证明:我们考虑归纳法,设已经考虑了前 ii 个区间,显然 i=1i = 1 时成立。
现在我们要考虑第 i+1i + 1 个区间,由于前 ii 个已经是最优解了,如果可以放置 i+1i + 1 个,显然仍是最优解(结尾是单调的,不可能再放之前不能放的区间)。如果不能放置 i+1i + 1 个,设前 ii 个区间已经放置了 kk 个,那么对于 i+1i + 1 个区间不存在 k+1k + 1 个解。问题变为要尽量缩段当前右端点的距离,而我们的替换方法一定能使得右端点左移最多,所以仍然是最优解。

于是使用一个大根堆就可以快速查询最大值,复杂度:O(nlogn)O(n\log n)

代码

//  Created by Sengxian on 08/25/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 1029 贪心
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int ReadInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}

const int maxn = 150000 + 3;
typedef pair<int, int> pi;
pi a[maxn];
int n;

int main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
#endif
    n = ReadInt();
    for (int i = 0; i < n; ++i) a[i].second = ReadInt(), a[i].first = ReadInt();
    sort(a, a + n);
    priority_queue<int> pq;
    int ans = 0; ll ti = 0;
    for (int i = 0; i < n; ++i)
        if (ti + a[i].second <= a[i].first) ans++, ti += a[i].second, pq.push(a[i].second);
        else if (!pq.empty() && pq.top() > a[i].second)
            ti -= pq.top() - a[i].second, pq.pop(), pq.push(a[i].second);
    printf("%d\n", ans);
    return 0;
}