题解 P4053 【[JSOI2007]建筑抢修】

lx_zjk · 2019-10-02 08:12:32 · 题解

一道比较不错的贪心题

可以用反悔操作

总的贪心思路就是先将所有的产品按end排序 然后一个一个扫描去

if (last + a[i].cost <= a[i].end) {
    last += a[i].cost;
    q.push(a[i]);
    cnt ++ ;
}

至于为什么要用一个堆 等会儿再说

操作儿 ：反悔操作

对于当前影响最大的商品一定是 max(a[].cost)

堆的最用就是帮你找到这个产品

然后就是反悔操作的代码了

if (last + a[i].cost > a[i].end) {
    if (!q.empty() && q.top().cost > a[i].cost && last - q.top().cost + a[i].cost <= a[i].end) {
                last -= q.top().cost;
                q.pop();
                q.push(a[i]);
                last += a[i].cost;
            }
        }

完整版代码

code

//
//  main.cpp
//  tmp
//
//  Created by Hock on 2019/10/1.
//  Copyright © 2019 Hock. All rights reserved.
//

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <cstring>

using namespace std;

typedef unsigned long long ll;

const int INF = 2139062143;

#define DEBUG(x) std::cerr << #x << ' = ' << x << std::endl

inline int read() {
    int f = 1, x = 0;char ch;
    do {ch = getchar();if (ch == '-')f = -1;} while (ch > '9' || ch < '0');
    do {x = x * 10 + ch - '0';ch = getchar();} while (ch >= '0' && ch <= '9');
    return f * x;
}

const int MAX_N = 150000;

int n;

struct Node {
    int cost, end;
    bool operator < (const Node & rhs) const {
        return cost < rhs.cost;
    }
} a[MAX_N];

bool cmp (Node a, Node b) {
    return a.end < b.end;
}

int main () {
    n = read();
    for (int i = 1; i <= n; i ++ ) {
        a[i].cost = read();
        a[i].end = read();
    }
    sort (a + 1, a + n + 1, cmp);
    int last = 0, cnt = 0;
    priority_queue < Node > q;
    for (int i = 1; i <= n; i ++ ) {
        if (last + a[i].cost <= a[i].end) {
            last += a[i].cost;
            cnt ++ ;
            q.push(a[i]);
        } else if (last + a[i].cost > a[i].end) {
            if (!q.empty() && q.top().cost > a[i].cost && last - q.top().cost + a[i].cost <= a[i].end) {
                last -= q.top().cost;
                q.pop();
                q.push(a[i]);
                last += a[i].cost;
            }
        }
    }
    cout << cnt << endl;
    return 0;
}