P4053 [JSOI2007] 建筑抢修

#include<bits/stdc++.h>//万能头
using namespace std;
struct stu{ //定义结构体
	long long t1,t2; //修理耗时,结束时间
};
bool cmp(stu a, stu b){ 
	return a.t2<b.t2; //先报废的先修
}
long long n,f,ans;//建筑个数,当前时间,最多能抢修建筑个数
int main() 
{
    cin>>n;//输入
    vector<stu>a(n);
    vector<long long>v;//动态数组
    for(int i=0; i<n; i++) cin >>a[i].t1>>a[i].t2;//输入
    sort(a.begin(),a.end(),cmp);//按报废时间从早到晚排序
    for(int i=0; i<n; i++){ //开始判断
        if(f+a[i].t1<=a[i].t2){ //如果能修
            f+=a[i].t1; //当前时间加上维修时间
            v.insert(lower_bound(v.begin(),v.end(),a[i].t1),a[i].t1); //有序插入当前建筑维修时间
            ans++; //答案加一
        } 
		else if(!v.empty() && v.back()>a[i].t1){ //贪心（替换耗时更长的任务）
            f+=a[i].t1-v.back(); //更新当前时间
            v.pop_back(); //移除最长耗时的任务
            v.insert(lower_bound(v.begin(),v.end(),a[i].t1),a[i].t1); //插入新任务
        }
	}
    cout<<ans;//输出答案
    return 0;
}