贪心,按截止时间排序,然后按截止时间从小到大枚举维修的建筑,如果之前修理建筑的总时间+当前修理时间<=截止时间,那么答案+1,否则如果之前修理过的建筑中最大的修理时间>当前建筑修理时间,那么替换掉之前修理的那座建筑。
代码
#include<cstdio>
#include<queue>
#include<algorithm>
#define mp make_pair
#define fi first
#define sc second
using namespace std;
const int N = ;
priority_queue<int> Q;
struct g{
int a,b;
}v[N];
bool cmp(g u,g v)
{
if (u.b==v.b)
return u.a>v.a;
return u.b<v.b;
}
int n,sum,i,ans;
int main()
{
scanf("%d",&n);
for (i=;i<=n;i++)
scanf("%d%d",&v[i].a,&v[i].b);
sort(v+,v++n,cmp);
for (i=;i<=n;i++)
{
//printf("%d %d\n",sum,v[i].b);
if (sum+v[i].a>v[i].b)
{
if ((!Q.empty())&&(Q.top()>v[i].a))
{
sum-=Q.top();
sum+=v[i].a;
Q.pop();
Q.push(v[i].a);
}
}
else
{
Q.push(v[i].a);
sum+=v[i].a;
ans++;
}
}
printf("%d\n",ans);
}