[JSOI2007]建筑抢修

题意：有n个建筑需要抢修，给出这n个建筑的抢修时间和截止时间，求最多可以抢修多少建筑？

思路：按截止时间升序排列，用优先队列维护可维修的建筑的持续时间，因为截止时间是升序的，所以当遇到无法及时维修的建筑时，如果小于优先队列中最大的持续时间，可以替换，这样优先队列中数据量不变，总时间减少，相当于优化了选择。

代码：

#include<bits/stdc++.h>

using namespace std;
#define ll long long
#define inf 1000000007

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = (x<<1) + (x<<3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}

struct w
{
    ll x, y;
} w[200005];

bool cmp(struct w a,struct w b)
{
    return a.y<b.y;
}

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%lld%lld",&w[i].x,&w[i].y);
    }
    sort(w,w+n,cmp);
    priority_queue<ll> que;
    ll t=0;
    for(int i=0;i<n;i++)
    {
        if(t+w[i].x<=w[i].y)
        {
            que.push(w[i].x);
            t=t+w[i].x;
        }
        else
        {
            ll p=que.top();
            if(p>w[i].x)
            {
                t=t-p;
                que.pop();
                que.push(w[i].x);
                t=t+w[i].x;
            }
        }
    }
    cout << que.size() << endl;
    return 0;
}