[bzoj1029]建筑抢修<贪心>

时间:2021-07-12 07:17:59

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1029

解析:这也算bzoj中比较简单的一道题,其实想通了就是非常的简单。

   这题用贪心的方式,我们先按照结束时间从小到大排,然后记录当前花费时间,只要可以继续修理就修理,如果不能修理(修理时间大于结束时间),就判断之前的操作中耗时最大的修理是不是比现在的修理时间更久,如果久,就放弃之前的那次修理,转而选择现在的这次修理(这个地方要好好想想,因为是按照结束时间的大小来从小到大执行的,是符合最终答案的)

然后我们通过样例来说明一下这个过程。

样例:                                                按照结束时间排序后的样例:

100 200                                                                                         100 200

200 1300                                                                                       1000 1250

1000 1250                                                                                     200 1300

2000 3200                                                                                     2000 3200

首先修第一个,耗时100,不大于结束时间200;

判断第二个,单个耗时1000,总耗时1100,不大于结束时间1250,加入第二个;

判断第三个,单个耗时200,总耗时1300,不大于结束时间1300,加入第三个;

判断第四个,单个耗时2000,总耗时3300,大于结束时间3200,且单个耗时2000大于之前最大耗时1000,不加入第四个;

所以最后维修3个;

但是这是测试样例,可以看出组合方式有几种都可以满足3种,有一句话说的好,测试数据是万能的,所以还是建议自己亲自去举个例子来看

然后就是代码:

 #include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstdlib>
#include<cmath>
#define maxn 150005
using namespace std; struct node{
int t1,t2;
}t[maxn]; int n,m,ans,tot;
int maxt; int comp(void const*a,void const*b)
{
return(*(struct node*)a).t2>(*(struct node*)b).t2?:-;
} priority_queue<int>q; int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
{
int a,b;
scanf("%d%d",&a,&b);
t[i].t1=a;t[i].t2=b;
}
qsort(t,n+,sizeof(t[]),comp);
for(int i=;i<=n;i++)
{
if(ans+t[i].t1<=t[i].t2)
{
q.push(t[i].t1);
ans+=t[i].t1;tot++;
}else{
if(t[i].t1<q.top())
{
ans-=q.top();
ans+=t[i].t1;
q.pop();
q.push(t[i].t1);
} } }
printf("%d",tot); }