【贪心】【堆】bzoj1029 [JSOI2007]建筑抢修

按完成时限排序,一个个修复。
若当前建筑花费时间+之前花费的总时间不超过时限,则ans++;
否则,从之前已修复的建筑中挑一个耗时最多的,与当前建筑比较,若当前建筑更优,则更新ans。

 #include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
priority_queue<int,vector<int> >Heap;
struct Point{int x,y;};
bool cmp(const Point &a,const Point &b){return a.y<b.y;}
int n,v,used,ans=;
Point a[];
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)scanf("%d%d",&a[i].x,&a[i].y);
sort(a+,a+n+,cmp);
used=a[].x;Heap.push(a[].x);
for(int i=;i<=n;i++)
{
if(used+a[i].x<=a[i].y)
{
Heap.push(a[i].x);
used+=a[i].x;
ans++;
continue;
}
v=Heap.top();
if(v>a[i].x)
{
Heap.pop();
Heap.push(a[i].x);
used+=(a[i].x-v);
}
}
printf("%d\n",ans);
}
上一篇:[BZOJ1029] [JSOI2007]建筑抢修(贪心 + 优先队列)


下一篇:BZOJ 1029: [JSOI2007]建筑抢修 堆+贪心