bzoj1029: [JSOI2007]建筑抢修(堆+贪心)

1029: [JSOI2007]建筑抢修

题目:传送门

题解:

   一道以前就做过的水题(找个水题签个到嘛...)

   很明显就是一道贪心题,这里我们用一个堆来维护

   具体看代码吧,很容易YY所以不讲

代码:

 #include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
typedef long long LL;
struct node
{
LL t1,t2;
}a[];
priority_queue<int,vector<int>,less<int> > q;
bool cmp(node n1,node n2)
{
if(n1.t2>n2.t2)return false;
if(n1.t2<n2.t2)return true;
if(n1.t1<n2.t1)return true;
if(n1.t1>n2.t1)return false;
return true;
}
LL n;
int main()
{
scanf("%lld",&n);
for(int i=;i<=n;i++)
scanf("%lld%lld",&a[i].t1,&a[i].t2);
sort(a+,a+n+,cmp);
LL ans=,now=;
for(int i=;i<=n;i++)
{
if(now+a[i].t1<=a[i].t2)
{
ans++;
now+=a[i].t1;
q.push(a[i].t1);
}
else
{
LL t=q.top();
if(a[i].t1<t)
{
q.pop();
now-=t-a[i].t1;
q.push(a[i].t1);
}
}
}
printf("%lld\n",ans);
return ;
}
上一篇:Nodejs 实现ESL内联FreeSWITCH设定说明


下一篇:###《Effective STL》--Chapter1