BZOJ 1029 JSOI2007 建筑抢修 贪心+堆
浏览数：26 /
时间：2015年06月09日
题目大意：n个建筑需要抢修，第i个建筑需要T1时间抢修，必须在T2时间之前抢修完毕，求最多能抢修多少建筑
首先我们对T2排序 然后依次修理 但是这样贪心显然是不正确的 比如说这组数据：
5
10 10
10 20
2 21
2 21
2 21
贪心只能修理前两个，而实际上最多可以修理4个
于是我们考虑修正贪心算法
比如说这组数据，当我们枚举到3的时候，虽然已经无法修理更多了，但是我们可以取消修理建筑1而改修理3，这样虽然不能更新ans 但是可以为后面的建筑节省时间
所以做法就很明确了
我们维护一个大根堆 每修理一栋建筑 我们就把这栋建筑的T1值加入堆 若当前无法修理 我们判断堆顶是否比这栋建筑的T1大 如果大 取消修理堆顶，改为修理当前建筑
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 150100
using namespace std;
struct construction{
int T1,T2;
bool operator < (const construction &x) const
{
return T2 < x.T2;
}
}buildings[M];
int n,ans,now,heap[M],top;
void Insert(int x)
{
heap[++top]=x;
int t=top;
while(t>1&&heap[t]>heap[t>>1])
swap(heap[t],heap[t>>1]),t>>=1;
}
void Pop()
{
heap[1]=heap[top--];
int t=2;
while(t<=top)
{
if(t<top&&heap[t+1]>heap[t])
++t;
if(heap[t]>heap[t>>1])
swap(heap[t],heap[t>>1]),t<<=1;
else
break;
}
}
int main()
{
int i;
cin>>n;
for(i=1;i<=n;i++)
scanf("%d%d",&buildings[i].T1,&buildings[i].T2);
sort(buildings+1,buildings+n+1);
for(i=1;i<=n;i++)
{
if(now+buildings[i].T1<=buildings[i].T2)
{
now+=buildings[i].T1;
++ans;
Insert(buildings[i].T1);
}
else
{
if(!top)
continue;
int temp=heap[1];
if( temp>buildings[i].T1 )
now=now+buildings[i].T1-temp,Pop(),Insert(buildings[i].T1);
}
}
cout<<ans<<endl;
}
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
