BZOJ 1029 - [JSOI2007]建筑抢修

#贪心 #优先队列

Published on 2016-08-26

描述

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

分析

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

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

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

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

于是使用一个大根堆就可以快速查询最大值，复杂度： $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;
}

Codeforces 711E - ZS and The Birthday Paradox BZOJ 1019 - [SHOI2008]汉诺塔

Sengxian's Blog

BZOJ 1029 - [JSOI2007]建筑抢修

描述

分析

代码