[JSOI2007]建筑抢修

ゝ一纸荒年。 2024-04-20 07:19 6阅读 0赞

⭐**简单说两句**⭐

> **作者：****后端小知识**
> 
> **CSDN**个人主页：[后端小知识][Link 1]
> 
> 🔎**GZH**：`后端小知识`
> 
> 🎉欢迎关注🔎点赞👍收藏⭐️留言📝

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

考虑到直接复制题目，或者截屏的方式不是很方便阅读，我就把直接题目链接放下面！  
题目传送门： [\[JSOI2007\]建筑抢修][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;
    }

【都看到这了，点点赞点点关注呗，爱你们】😚😚

![抽象工厂  引导关注][5a76cf4b74dee28cf9589be2f8214635.png]

**结语**

`谢谢你的阅读`，由于作者水平有限，难免有不足之处，若读者发现问题，还请批评，在留言区留言或者私信告知，我一定会尽快修改的。若各位大佬有什么好的解法，或者有意义的解法都可以在评论区展示额，万分谢谢。  
写作不易，望各位老板点点赞，加个关注!😘😘😘

💬

**作者：****后端小知识**

**CSDN**个人主页：[后端小知识][Link 1]

🔎**GZH**：`后端小知识`

🎉欢迎关注🔎点赞👍收藏⭐️留言📝

[Link 1]: https://blog.csdn.net/m0_46833224
[JSOI2007]: https://ac.nowcoder.com/acm/problem/20154
[5a76cf4b74dee28cf9589be2f8214635.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/70f3f90b458c4896a9ceed0f849d806c.png