【JSOI2007】【BZOJ1029】建筑抢修（贪心，堆）

problem

• n个建筑需要抢修
• 第i个建筑需要T1时间抢修，必须在T2时间之前抢修完毕
• 求最多能抢修多少建筑

solution

• 先按照 t2 从小到大排列（对于每一个建筑，我们肯定等它快到限制的时候再修复它。）
• 对于一个建筑,如果能修理就修理；
• 如果不能修，就比较他和前面修理了的建筑的修理时间。如果小于就交换（取消修理前面的建筑而改修理当前建筑，这样虽然不能更新ans 但是可以为后面的建筑节省时间
• 维护一个大根堆 每修理一栋建筑 我们就把这栋建筑的T1值加入堆 若当前无法修理 我们判断堆顶是否比这栋建筑的T1大。如果大，取消修理堆顶，改为修理当前建筑

codes

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn = 1100010;
struct node{ int t1, t2; }a[maxn];
bool cmp(node a, node b){return a.t2<b.t2; }
int main(){
    int n;  cin>>n;
    for(int i = 1; i <= n; i++)
        cin>>a[i].t1>>a[i].t2;
    sort(a+1,a+n+1,cmp);
    int now = 0, ans = 0;
    priority_queue<int>q;
    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 = now+a[i].t1-q.top();
            q.pop();  q.push(a[i].t1);
        }
    }
    cout<<ans<<'\n';
    return 0;
}
  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/80488004