建筑抢修 (大根堆+贪心+优先队列+快速排序+2重思想比较)

简介: 建筑抢修 (大根堆+贪心+优先队列+快速排序+2重思想比较)

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


输入格式



  第一行是一个整数N接下来N行每行两个整数T1,T2描述一个建筑:修理这个建筑需要T1秒,如果在T2秒之内还没有修理完成,这个建筑就报废了。


输出格式



  输出一个整数S,表示最多可以抢修S个建筑.N < 150,000; T1 < T2 < maxlongint


Sample Input


4
100 200
200 1300
1000 1250
2000 3200


Sample Output


3


题目分析,我们要抢修最多的建筑,首先我们把到期时间由大到小排列然后输出看有几个满足条件,然后当不出现可抢修的建筑的时候,我们把修建筑花的时间有大到小排列,然后找后面的看有没有比这个抢修时间花费少的如果有则替换掉进入下一个循环看满不满足,依次循环,最后得到答案。


听懂了记得给个赞鼓励一下,码字不易,用爱发电。


上ac代码。

f58230e9f063709cf3167704f4efdf14.gif


有事你就q我;QQ2917366383


学习算法

#include<iostream>
#include<algorithm>
#include<queue>
const int maxn=1e6+7;
using namespace std;
priority_queue<int>q;
struct yyds{int x,y;
}a[maxn];
int cmp(yyds w,yyds e)
{
  return w.y<e.y;
}
int main()
{
  int t,ans=0,tot=0;
  cin>>t;
  for(int i=1;i<=t;i++)
  {
    cin>>a[i].x>>a[i].y;
  }
  sort(a+1,a+1+t,cmp);
  for(int i=1;i<=t;i++)
  {
    if(tot+a[i].x<=a[i].y)
    {
      tot+=a[i].x;
      ans++;
      q.push(a[i].x);
    }
    else
    {
      if(a[i].x<q.top()&&q.top()!=0)
      {
        tot-=q.top()-a[i].x;
        q.pop();
        q.push(a[i].x);
      }     
    }
  }
  cout<<ans<<endl;
 } 
相关文章
|
人工智能 算法
【算法分析与设计】递归与分治策略(二)
【算法分析与设计】递归与分治策略
|
21天前
|
算法 开发者
【时间复杂度和空间复杂度之间的故事】
【时间复杂度和空间复杂度之间的故事】
16 5
|
机器学习/深度学习 算法 编译器
【算法分析与设计】递归与分治策略(一)
【算法分析与设计】递归与分治策略
|
搜索推荐
图解:快速排序算法之双边循环法
之前我们学习了冒泡排序,有没有比冒泡排序更快的排序算法呢?当然有,例如快速排序,归并排序,堆排序。接下来即将介绍的快速排序就是由冒泡排序演变而来的。
169 0
图解:快速排序算法之双边循环法
|
6月前
|
算法 搜索推荐
归并算法:分治而治的高效算法大揭秘(图文详解)
归并算法:分治而治的高效算法大揭秘(图文详解)
95 0
|
6月前
|
算法 vr&ar
1611F - ATM and Students详细题解(*1800,线段树维护前缀和;双指针算法(思维))
1611F - ATM and Students详细题解(*1800,线段树维护前缀和;双指针算法(思维))
41 0
|
算法 搜索推荐
分治法实现合并排序(归并排序),理解分治算法思想,实现分治算法的完美例子合并排序(含码源与解析)
分治法实现合并排序(归并排序),理解分治算法思想,实现分治算法的完美例子合并排序(含码源与解析)
179 0
|
存储 人工智能 算法
【算法分析与设计】回溯法(上)
【算法分析与设计】回溯法(上)
|
算法 搜索推荐 Windows
【算法分析与设计】递归与分治策略(三)
【算法分析与设计】递归与分治策略
|
存储 人工智能 算法
【算法分析与设计】动态规划(上)
【算法分析与设计】动态规划(上)