题目传送门
题意
有
n
n
n 个损坏的建筑，每个建筑修复需要
t
i
t_i
ti 时间，每个建筑如果在
d
i
d_i
di 时间仍然没有修好就会毁掉，问最多能修好多少个建筑。
解题方法
建筑在时间线上不断的毁掉，我们可以很容易的想到把
d
i
d_i
di 从小到大排序，如果在这个时间之后我们就把这个建筑毁掉，然后我们就以
d
i
d_i
di 为关键字排序，从小到大排序遍历，然后定义一个变量
n
o
w
now
now ，用来记录我们一共修了多长时间了，然后判断
n
o
w
+
t
i
now+t_i
now+ti 与
d
i
d_i
di 的关系，如果使小于等于的，那么我们就直接修，如果不是的话，我们就把之前修过的建筑并且耗时最长的去掉（如果这个时间大于这次修建需要的时间的话），只需要用一个大根堆就可以了，这样做一定会保证新的建筑一定能修完，这个样子可以为后面留出更多的时间。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std
;
struct node
{
long long t1
,t2
;
friend bool operator < (node x
,node y
)
{
return x
.t2
<y
.t2
;
}
}a
[3000000];
priority_queue
<int>q
;
int main()
{
long long n
;
scanf("%lld",&n
);
for(long long i
=1;i
<=n
;i
++)
{
long long x
,y
;
node t
;
scanf("%lld%lld",&x
,&y
);
a
[i
].t1
=x
;
a
[i
].t2
=y
;
}
sort(a
+1,a
+n
+1);
long long now
=0;
long long ans
=0;
for(long long i
=1;i
<=n
;i
++)
{
node x
;
x
=a
[i
];
if(now
+x
.t1
<=x
.t2
)
{
ans
++;
now
+=x
.t1
;
q
.push(x
.t1
);
}
else
{
long long fq
=q
.top();
if(fq
>x
.t1
)
{
q
.pop();
now
-=fq
;
now
+=x
.t1
;
q
.push(x
.t1
);
}
}
}
cout
<<ans
<<'\n';
return 0;
}
