洛谷 P4053 [JSOI2007]建筑抢修

题目传送门

反悔的贪心,先按照结束时间从小到大排序,往后扫.

如果能完成当前任务,就更新最后时刻,答案加1.

如果不能完成当前任务,就找在此之前可以完成的用的时间最多的那一个,比较一下,如果当前的这个任务时间更优,就把找到的那个任务删了,换成当前任务,更新最后时刻.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>

using namespace std;

int n,ans;
long long k,sum[150001];
struct kkk{
	long long l,r,st;
}e[150001];
priority_queue<kkk> q;

inline bool operator <(kkk s,kkk d) {
	return s.l < d.l;
}

inline bool cmp(kkk s,kkk d) {
	if(s.r == d.r) return s.l > d.l;
	return s.r < d.r;
}

int main() {
	scanf("%d",&n);
	for(int i = 1;i <= n; i++) {
		scanf("%lld%lld",&e[i].l,&e[i].r);
		e[i].st = e[i].r - e[i].l;
	}
	sort(e+1,e+n+1,cmp);
	for(int i = 1;i <= n; i++) {
		if(e[i].st >= k) {
			k = k + e[i].l;
			ans++;
			q.push(e[i]);
		}
		else {
			kkk o = q.top();
			if(o.l > e[i].l) {
				k = k - o.l + e[i].l;
				q.pop();
				q.push(e[i]);
			}
		}
	}
	printf("%d",ans);
	return 0;
}