BZOJ 1029: [JSOI2007]建筑抢修

贪心法

一开始以为是取线段问题……结果发现手算的样例过不去,然后才发现是时间可以接上去的...

和取线段问题类似,我们首先把所有的建筑按照结束时间点排序,每次拿到这个建筑,我们看看之前修理的所有建筑的时间和是多少,如果来得及修理就加入到维修的列表里去,但是如果来不及修理的话怎么办呢?由于之前的所有建筑都可以在截止时间前修好,我们可以删掉其中的某些建筑来满足当前考虑的这个点,但是我们显然最多删掉一个(否则的话总数会减少),那么删除掉哪个呢?当然是完成时间最大的那个啦!(注意这里如果完成时间最大的那个比当前考虑的建筑完成时间要短的话就跳过当前这个建筑,否则的话时间增加而维修的建筑数不变)  

于是我们就得到了一个这样的问题:动态插入一些点,每次寻找其中最大的,采用堆维护即可。

感觉贪心题的证明还是比较重要的,个人感觉自己的贪心是很弱的……

#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
const int N=150010;
typedef long long LL;
LL n,s,t,last;
struct ar{LL t1,t2;friend bool operator <(ar a,ar b){return a.t1<b.t1;}}b[N];
priority_queue<ar> q;
bool cmp(ar a,ar b){return a.t2<b.t2;}
void read(LL &x){char c;while((c=getchar())<'0'||c>'9');x=c-'0';while((c=getchar())>='0'&& c<='9') x=x*10+c-'0';}
int main(){
	//freopen("1029.in","r",stdin);freopen("1029.out","w",stdout);
	read(n);
	for(int i=1;i<=n;i++) read(b[i].t1),read(b[i].t2);
	sort(b+1,b+n+1,cmp);
	for(int i=1;i<=n;i++)
		if(t+b[i].t1<=b[i].t2) q.push(b[i]),s++,t+=b[i].t1;
		else if(!q.empty()){
			ar a=q.top();
			if(b[i].t1<a.t1) q.pop(),q.push(b[i]),t=t-a.t1+b[i].t1;
		}
	printf("%lld",s);
	return 0;
}