1029: [JSOI2007]建筑抢修

 

分析：

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

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

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

代码：

1 #include
     
       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
      
        a[150010];11 priority_queue
       
        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 }