建筑抢修 (大根堆+贪心+优先队列+快速排序+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;
 } 
相关文章
|
算法 数据挖掘 调度
【算法分析与设计】贪心算法(下)
【算法分析与设计】贪心算法(下)
【算法分析与设计】贪心算法(下)
|
人工智能 算法
【算法分析与设计】递归与分治策略(二)
【算法分析与设计】递归与分治策略
|
算法
快排三种递归及其优化,非递归和三路划分
快排三种递归及其优化,非递归和三路划分
63 0
|
机器学习/深度学习 算法 编译器
【算法分析与设计】递归与分治策略(一)
【算法分析与设计】递归与分治策略
|
搜索推荐
图解:快速排序算法之双边循环法
之前我们学习了冒泡排序,有没有比冒泡排序更快的排序算法呢?当然有,例如快速排序,归并排序,堆排序。接下来即将介绍的快速排序就是由冒泡排序演变而来的。
181 0
图解:快速排序算法之双边循环法
|
搜索推荐
“掌握更多的快速排序技巧:三路划分、双路快排和非递归的深入理解”(上)
“掌握更多的快速排序技巧:三路划分、双路快排和非递归的深入理解”(上)
175 0
|
算法 搜索推荐
分治法实现合并排序(归并排序),理解分治算法思想,实现分治算法的完美例子合并排序(含码源与解析)
分治法实现合并排序(归并排序),理解分治算法思想,实现分治算法的完美例子合并排序(含码源与解析)
186 0
|
算法 搜索推荐 Windows
【算法分析与设计】递归与分治策略(三)
【算法分析与设计】递归与分治策略
|
机器学习/深度学习 存储 算法
【算法分析与设计】贪心算法(上)
【算法分析与设计】贪心算法(上)
|
算法
图解:快速排序之单边循环法
单边循环法是快速排序的算法之一,之前的双边循环法从数列的两边交替遍历元素,虽然更加直观,不过代码实现起来相对复杂。而单边循环法就要简单多了,只需要从数组的一边对元素进行遍历和交换即可。
200 0
图解:快速排序之单边循环法