[JSOI2007]建筑抢修

[JSOI2007]建筑抢修

https://ac.nowcoder.com/acm/problem/20154

题意:

张老师的旅行看上去很像但是并不一样,这题比较水,直接贪心就可以了。

  1. 对截止时间早晚来贪心。
  2. 当出现建筑无法修复的时候,如果修复这个建筑所需要消耗的时间,比我之前所修复的所有建筑里最耗时的要短,那就修复这个,放弃之前的那个。

两段贪心,使用大根堆来实现。

#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
using namespace std;
typedef long long ll;
const int N = 1e5 + 5e4 + 7;
const ll mod = 1e9 + 7;
struct item {
    ll cost, end;
    bool operator<(const item& x) const { return end < x.end; }
} p[N];
int main() {
    ll n;
    sc(n);
    for (int i = 1; i <= n; ++i) sc(p[i].cost), sc(p[i].end);
    sort(p + 1, p + 1 + n);
    priority_queue<ll> q;
    ll now = 0, ans = 0;
    for (int i = 1; i <= n; ++i) {
        if (now + p[i].cost <= p[i].end) {
            ++ans;
            now += p[i].cost;
            q.push(p[i].cost);
        } else if (!q.empty() && q.top() > p[i].cost) {
            now += (p[i].cost - q.top());
            q.pop();
            q.push(p[i].cost);
        }
    }
    pr(ans);
    return 0;
}
算法竞赛之路 文章被收录于专栏

整理、记录算法竞赛的好题

全部评论

相关推荐

点赞 评论 收藏
分享
05-29 22:11
门头沟学院 Java
Elastic90:抛开学历造假不谈,这公司的招聘需求也挺怪的,Java开发还要求你有图文识别、移动端开发和c++的经验,有点逆天了。
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务