Description
小刚在玩JSOI提供的一个称之为“建筑抢修”的电脑游戏：经过了一场激烈的战斗，T部落消灭了所有z部落的入侵者。但是T部落的基地里已经有N个建筑设施受到了严重的损伤，如果不尽快修复的话，这些建筑设施将会完全毁坏。现在的情况是：T部落基地里只有一个修理工人，虽然他能瞬间到达任何一个建筑，但是修复每个建筑都需要一定的时间。同时，修理工人修理完一个建筑才能修理下一个建筑，不能同时修理多个建筑。如果某个建筑在一段时间之内没有完全修理完毕，这个建筑就报废了。你的任务是帮小刚合理的制订一个修理顺序，以抢修尽可能多的建筑。
Input
第一行是一个整数N，接下来N行每行两个整数T1,T2描述一个建筑：修理这个建筑需要T1秒，如果在T2秒之内还没有修理完成，这个建筑就报废了。
Output
输出一个整数S，表示最多可以抢修S个建筑。 数据范围： N<150000，T1
Sample Input
4
100 200
200 1300
1000 1250
2000 3200
Sample Output
3
先对t2进行排序，然后一个个加入
如果now+t1<=t2，就直接加入
如果now+t1>t2，那么就用它和已经加入的时间最大的比较，如果t1比它小就替换它
用大根堆维护最大时间
const
maxn=; type
node=record
t1,t2:longint;
end; var
a:array[..maxn]of node;
n:longint; procedure swap(var x,y:node);
var
t:node;
begin
t:=x;x:=y;y:=t;
end; procedure sort(l,r:longint);
var
i,j,y:longint;
begin
i:=l;j:=r;
y:=a[(l+r)>>].t2;
repeat
while a[i].t2<y do
inc(i);
while a[j].t2>y do
dec(j);
if i<=j then
begin
swap(a[i],a[j]);
inc(i);
dec(j);
end;
until i>j;
if i<r then sort(i,r);
if j>l then sort(l,j);
end; procedure init;
var
i:longint;
begin
read(n);
for i:= to n do
with a[i] do
read(t1,t2);
sort(,n);
end; var
q:array[..maxn]of node;
now,tot:longint; procedure down(x:longint);
var
i:longint;
begin
i:=x<<;
while i<=tot do
begin
if (i<tot) and (q[i+].t1>q[i].t1) then inc(i);
if q[x].t1<q[i].t1 then
begin
swap(q[x],q[i]);
x:=i;
i:=x<<;
end
else break;
end;
end; procedure up(x:longint);
var
i:longint;
begin
while x> do
begin
i:=x>>;
if q[x].t1>q[i].t1 then
begin
swap(q[i],q[x]);
x:=i;
i:=x>>;
end
else break;
end;
end; procedure work;
var
i:longint;
begin
for i:= to n do
if now+a[i].t1<=a[i].t2 then
begin
inc(tot);
q[tot]:=a[i];
up(tot);
inc(now,a[i].t1);
end
else
if a[i].t1<q[].t1 then
begin
now:=now-q[].t1+a[i].t1;
swap(a[i],q[]);
down();
end;
write(tot);
end; begin
init;
work;
end.