[JSOI2007]建筑抢修

简介: [JSOI2007]建筑抢修

题目: [JSOI2007]建筑抢修 ,哈哈,我们今天来看一道贪心算法的题嘛,这是选自JSOI上的一道题,好了,我们一起来看看题意吧:

考虑到直接复制题目,或者截屏的方式不是很方便阅读,我就把直接题目链接放下面!

题目传送门: [JSOI2007]建筑抢修

思路:

这道题可以采用反悔贪心算法,具体的就看代码吧,有注释的!

我们来看看成功AC的代码吧:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n;
struct ty{
    int t1,t2;
}a[150010];
int cmp(ty e1,ty e2){//排序方式
    return e1.t2<e2.t2;
}
priority_queue<int> q;//定义一个大根堆
ll ans=0,now=0;
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i].t1>>a[i].t2;
    sort(a+1,a+1+n,cmp);//按照截止时间短的方式排序
    for(int i=1;i<=n;i++){
        if(now+a[i].t1<=a[i].t2){//若加入的建筑可以修就直接修
            ans++;
            now+=a[i].t1; q.push(a[i].t1);//加上当前建筑需要修的时间,并把当前需要修的时间加入堆里
        }else{//加入的建筑不可以直接修
            if(a[i].t1<q.top()){//我们看看是否可以后悔修上一个建筑
                now-=q.top();now+=a[i].t1; q.pop();q.push(a[i].t1);
            }
        }
    }
    cout<<ans;
    return 0;
}


目录
打赏
0
0
0
0
0
分享
相关文章
智能建筑管理系统:建筑能效的优化
【10月更文挑战第23天】智能建筑管理系统(IBMS)通过集成信息技术、自动化和通信技术,实现对建筑内设施的综合监控与管理,优化能效,提升舒适性和安全性。本文介绍IBMS的功能特点、应用成效及未来发展趋势,展示其在建筑能效优化中的重要作用。
厂区车辆导航系统,科技助力工业运输生产安全
近期食品安全事件暴露工业运输安全漏洞,煤油罐车未经清洗运输食用油,引发关注。厂区货车面临监管难、操作不规范、效率低和安全隐患等问题。为解决这些挑战,车辆定位导航系统提出,包括精准定位追踪、智能调度、规范操作提示与监控、历史轨迹查询与审计及紧急响应功能,显著提升监管效率、规范操作、优化运输并增强安全。维小帮的系统为此提供了创新解决方案。
130 13
厂区车辆导航系统,科技助力工业运输生产安全
城市建筑通视分析 通视分析
城市建筑通视分析 通视分析
55 0
绿色建筑真的可以帮助应对气候变化吗?
绿色建筑通过提高能源效率和促进更大的绿色和可持续社区,努力减缓气候变化的影响。
366 0
绿色建筑真的可以帮助应对气候变化吗?
未来互联城市的面向未来的建筑
智能城市正稳步成为现实,这要归功于工程师们,他们通过集成开放的、可互操作的物联网平台,为未来的发展提供了保障,这些平台在未来几年内可以得到增强、发展和利用。随着技术的不断发展,现在使用的平台、数据和基础设施的设计必须考虑到未来的可能性。
404 0
未来互联城市的面向未来的建筑