建筑抢修（堆优先队列和贪心的结合）

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

Input

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

Output

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

Sample Input

Sample Output

3
个人体会：好不容易简单学会了简单贪心，堆这一关确实卡住了，借鉴了网上的思路。其实认真想还是可以想到的，在贪心的基础上，若遇到不能抢修的就依次将推顶的元素拿出来，继续修理，这样即使后面存在最优解也能一起算上去了。
就是我们维护一个大根堆，每修理一栋建筑，我们就把这栋建筑的start值加入堆，若当前无法修理，我们判断堆顶是否比这栋建筑的start大。如果大，取消修理堆顶，改为修理当前建筑
同时给上stl优先数列中一般数据和结构体的代码
一般数据从大到小是priority_queque<int>pq;反过来就是priority_queue<int,vector<int>,greater<int>>pq;
对于结构体

 1 Struct Node
 2 {
 3    int priority;
 4   int value;
 5 friend bool operator < (Node t1,Node t2)
 6 {
 7    return t1.priority<t2.priority;
 8 }
 9 };
10 priority_queue<Node>pq;

现在给出题目正解

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<queue>
 4 #include<algorithm>
 5 using namespace std;
 6 struct time
 7 {
 8     int start;
 9     int send;
10 
11 }t[150005];
12 bool cmp(const struct time &a,const struct time& b)
13 {
14     return a.send<b.send;
15 
16 }
17 int main()
18 {
19     int n;
20     cin>>n;
21     priority_queue<int >s;
22     int ti=0;
23     int sum=0;
24    for(int i=0;i<n;i++)
25     cin>>t[i].start>>t[i].send;
26     sort(t,t+n,cmp);
27     for(int i=0;i<n;i++)
28       {
29           if(t[i].start+ti<=t[i].send) {ti+=t[i].start;s.push(t[i].start);sum++;}
30           else  if(t[i].start<s.top())
31           {
32               ti=ti-s.top()+t[i].start;
33               s.pop();
34               s.push(t[i].start);
35 
36 }
37 }
38     cout<<sum<<endl;
39    return 0;
40 
41 }

建筑抢修（堆优先队列和贪心的结合）

相关推荐