1029: [JSOI2007]建筑抢修

https://www.lydsy.com/JudgeOnline/problem.php?id=1029

分析：

　　维护一个大根堆，记录所有修过的点中的修理时间。

　　首先按结束时间排序，依次取出结束时间较小的，如果当前的与以前的不冲突，那么直接加入，ans++。

　　否则，取出堆中的修理花费时间最大的y，比较前的x与y，如果x修理时间更小，那么可以不修y，修理x。而y的修理时间比x大，所以x是一定能够修理的。

代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 
 5 inline int read() {
 6     int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
 7     for (;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
 8 }
 9 
10 pair<int,int> a[150010];
11 priority_queue<int>q;
12 
13 int main() {
14     int n = read();
15     for (int i=1; i<=n; ++i) //second为修理时间，first为结束时间 
16         a[i].second = read(),a[i].first = read();
17     sort(a+1,a+n+1);
18     int ans = 0,now = 0;
19     for (int i=1; i<=n; ++i) { // 按结束时间依次取出 
20         if (now + a[i].second <= a[i].first) { // 时间不冲突 
21             ++ans;
22             now += a[i].second;
23             q.push(a[i].second);
24         }
25         else { // 时间冲突，同样是修理一个，修理用时少的，让后面有更多的选择 
26             if (q.empty()) continue; // --!q.empry() 
27             int x = q.top();
28             if (x <= a[i].second) continue;
29             now -= x;now += a[i].second;
30             q.pop();
31             q.push(a[i].second);
32         }
33     }
34     cout << ans;
35     return 0;
36 }