正文
1029: [JSOI2007]建筑抢修
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
1029: [JSOI2007]建筑抢修
Time Limit: 4 Sec Memory Limit: 162 MB
Submit: 2382 Solved: 1033
[Submit][Status]
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
HINT
Source
题解：啊啊啊啊啊又脑抽了（phile：我竟无言以对了 HansBug：唉，这就是搞了一星期吴仲华杯的后果）唉。。手生了没办法——珍爱生命，远离吴仲华杯（HansBug：反正再也没有了= =）！！！23333。。。好了思路——这是一个经典的贪心问题先按照deadline从小到大排序，然后每次保留一个当前消耗时间，假如已经消耗的时间+当前任务用时<=当前任务deadline的话，那就直接加进来；假如已消耗时间+当前任务用时>当前任务deadline的话，那检查一下当前任务耗时是否不比任何一次之前进行的任务都大，如果不是的话加进来，并把之前那个最大的扔出去；否则凉拌。。。（由于N<=150000，所以建议用大根堆维护，本萌妹还是继续用我萌萌哒左偏树，mua~~）
var
i,j,k,m,n,head:longint;
l:int64;
a,lef,rig,fix,b,c,d:array[..] of longint;
function min(x,y:longint):longint;inline;
begin
if x<y then min:=x else min:=y;
end;
function max(x,y:longint):longint;inline;
begin
if x>y then max:=x else max:=y;
end;
procedure swap(var x,y:longint);inline;
var z:longint;
begin
z:=x;x:=y;y:=z;
end;
procedure sort(l,r:longint);inline;
var i,j,x,y:longint;
begin
i:=l;j:=r;
x:=c[(i+j) div ];
repeat
while c[i]<x do inc(i);
while c[j]>x do dec(j);
if i<=j then
begin
swap(c[i],c[j]);
swap(d[i],d[j]);
inc(i);dec(j);
end;
until i>j;
if l<j then sort(l,j);
if i<r then sort(i,r);
end;
procedure merge(var x,y:longint);inline;
begin
if x= then swap(x,y);
if y= then exit;
if a[x]<a[y] then swap(x,y);
merge(rig[x],y);
fix[x]:=max(fix[lef[x]],fix[rig[x]])+;
if fix[lef[x]]<fix[rig[x]] then swap(lef[x],rig[x]);
end;
procedure cuthead(var head:longint);inline;
begin
if head= then exit;
merge(lef[head],rig[head]);
head:=lef[head];
end;
begin
readln(n);
for i:= to n do readln(d[i],c[i]);
sort(,n);l:=;
head:=;m:=;k:=;
fillchar(a,sizeof(a),);
fillchar(lef,sizeof(lef),);
fillchar(rig,sizeof(rig),);
fillchar(fix,sizeof(fix),);
for i:= to n do
begin
if int64(l+int64(d[i]))<=int64(c[i]) then
begin
l:=int64(l+int64(d[i]));inc(k);
inc(m);a[m]:=d[i];
j:=m;merge(head,j);
end
else
begin
if (int64(d[i])<int64(a[head])) then
begin
l:=int64(l+int64(d[i])-int64(a[head]));
inc(m);a[m]:=d[i];
cuthead(head);j:=m;
merge(head,j);
end;
end;
end;
writeln(k);
readln;
end.
小刚在玩JSOI提供的一个称之为“建筑抢修”的电脑游戏：经过了一场激烈的战斗，T部落消灭了所有z部落的入侵者。但是T部落的基地里已经有N个建筑设施受到了严重的损伤，如果不尽快修复的话，这些建筑设施将会完全毁坏。现在的情况是：T部落基地里只有一个修理工人，虽然他能瞬间到达任何一个建筑，但是修复每个建筑都需要一定的时间。同时，修理工人修理完一个建筑才能修理下一个建筑，不能同时修理多个建筑。如果某个建筑在一段时间之内没有完全修理完毕，这个建筑就报废了。你的任务是帮小刚合理的制订一个修理顺序，以抢修尽可能多的建筑。
第一行是一个整数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
HINT
Source
题解：啊啊啊啊啊又脑抽了（phile：我竟无言以对了 HansBug：唉，这就是搞了一星期吴仲华杯的后果）唉。。手生了没办法——珍爱生命，远离吴仲华杯（HansBug：反正再也没有了= =）！！！23333。。。好了思路——这是一个经典的贪心问题先按照deadline从小到大排序，然后每次保留一个当前消耗时间，假如已经消耗的时间+当前任务用时<=当前任务deadline的话，那就直接加进来；假如已消耗时间+当前任务用时>当前任务deadline的话，那检查一下当前任务耗时是否不比任何一次之前进行的任务都大，如果不是的话加进来，并把之前那个最大的扔出去；否则凉拌。。。（由于N<=150000，所以建议用大根堆维护，本萌妹还是继续用我萌萌哒左偏树，mua~~）
var
i,j,k,m,n,head:longint;
l:int64;
a,lef,rig,fix,b,c,d:array[..] of longint;
function min(x,y:longint):longint;inline;
begin
if x<y then min:=x else min:=y;
end;
function max(x,y:longint):longint;inline;
begin
if x>y then max:=x else max:=y;
end;
procedure swap(var x,y:longint);inline;
var z:longint;
begin
z:=x;x:=y;y:=z;
end;
procedure sort(l,r:longint);inline;
var i,j,x,y:longint;
begin
i:=l;j:=r;
x:=c[(i+j) div ];
repeat
while c[i]<x do inc(i);
while c[j]>x do dec(j);
if i<=j then
begin
swap(c[i],c[j]);
swap(d[i],d[j]);
inc(i);dec(j);
end;
until i>j;
if l<j then sort(l,j);
if i<r then sort(i,r);
end;
procedure merge(var x,y:longint);inline;
begin
if x= then swap(x,y);
if y= then exit;
if a[x]<a[y] then swap(x,y);
merge(rig[x],y);
fix[x]:=max(fix[lef[x]],fix[rig[x]])+;
if fix[lef[x]]<fix[rig[x]] then swap(lef[x],rig[x]);
end;
procedure cuthead(var head:longint);inline;
begin
if head= then exit;
merge(lef[head],rig[head]);
head:=lef[head];
end;
begin
readln(n);
for i:= to n do readln(d[i],c[i]);
sort(,n);l:=;
head:=;m:=;k:=;
fillchar(a,sizeof(a),);
fillchar(lef,sizeof(lef),);
fillchar(rig,sizeof(rig),);
fillchar(fix,sizeof(fix),);
for i:= to n do
begin
if int64(l+int64(d[i]))<=int64(c[i]) then
begin
l:=int64(l+int64(d[i]));inc(k);
inc(m);a[m]:=d[i];
j:=m;merge(head,j);
end
else
begin
if (int64(d[i])<int64(a[head])) then
begin
l:=int64(l+int64(d[i])-int64(a[head]));
inc(m);a[m]:=d[i];
cuthead(head);j:=m;
merge(head,j);
end;
end;
end;
writeln(k);
readln;
end.
输出一个整数S，表示最多可以抢修S个建筑。 数据范围： N<150000，T1
4
100 200
200 1300
1000 1250
2000 3200
100 200
200 1300
1000 1250
2000 3200
Sample Output
3
HINT
Source
题解：啊啊啊啊啊又脑抽了（phile：我竟无言以对了 HansBug：唉，这就是搞了一星期吴仲华杯的后果）唉。。手生了没办法——珍爱生命，远离吴仲华杯（HansBug：反正再也没有了= =）！！！23333。。。好了思路——这是一个经典的贪心问题先按照deadline从小到大排序，然后每次保留一个当前消耗时间，假如已经消耗的时间+当前任务用时<=当前任务deadline的话，那就直接加进来；假如已消耗时间+当前任务用时>当前任务deadline的话，那检查一下当前任务耗时是否不比任何一次之前进行的任务都大，如果不是的话加进来，并把之前那个最大的扔出去；否则凉拌。。。（由于N<=150000，所以建议用大根堆维护，本萌妹还是继续用我萌萌哒左偏树，mua~~）
var
i,j,k,m,n,head:longint;
l:int64;
a,lef,rig,fix,b,c,d:array[..] of longint;
function min(x,y:longint):longint;inline;
begin
if x<y then min:=x else min:=y;
end;
function max(x,y:longint):longint;inline;
begin
if x>y then max:=x else max:=y;
end;
procedure swap(var x,y:longint);inline;
var z:longint;
begin
z:=x;x:=y;y:=z;
end;
procedure sort(l,r:longint);inline;
var i,j,x,y:longint;
begin
i:=l;j:=r;
x:=c[(i+j) div ];
repeat
while c[i]<x do inc(i);
while c[j]>x do dec(j);
if i<=j then
begin
swap(c[i],c[j]);
swap(d[i],d[j]);
inc(i);dec(j);
end;
until i>j;
if l<j then sort(l,j);
if i<r then sort(i,r);
end;
procedure merge(var x,y:longint);inline;
begin
if x= then swap(x,y);
if y= then exit;
if a[x]<a[y] then swap(x,y);
merge(rig[x],y);
fix[x]:=max(fix[lef[x]],fix[rig[x]])+;
if fix[lef[x]]<fix[rig[x]] then swap(lef[x],rig[x]);
end;
procedure cuthead(var head:longint);inline;
begin
if head= then exit;
merge(lef[head],rig[head]);
head:=lef[head];
end;
begin
readln(n);
for i:= to n do readln(d[i],c[i]);
sort(,n);l:=;
head:=;m:=;k:=;
fillchar(a,sizeof(a),);
fillchar(lef,sizeof(lef),);
fillchar(rig,sizeof(rig),);
fillchar(fix,sizeof(fix),);
for i:= to n do
begin
if int64(l+int64(d[i]))<=int64(c[i]) then
begin
l:=int64(l+int64(d[i]));inc(k);
inc(m);a[m]:=d[i];
j:=m;merge(head,j);
end
else
begin
if (int64(d[i])<int64(a[head])) then
begin
l:=int64(l+int64(d[i])-int64(a[head]));
inc(m);a[m]:=d[i];
cuthead(head);j:=m;
merge(head,j);
end;
end;
end;
writeln(k);
readln;
end.
Source
题解：啊啊啊啊啊又脑抽了（phile：我竟无言以对了 HansBug：唉，这就是搞了一星期吴仲华杯的后果）唉。。手生了没办法——珍爱生命，远离吴仲华杯（HansBug：反正再也没有了= =）！！！23333。。。好了思路——这是一个经典的贪心问题先按照deadline从小到大排序，然后每次保留一个当前消耗时间，假如已经消耗的时间+当前任务用时<=当前任务deadline的话，那就直接加进来；假如已消耗时间+当前任务用时>当前任务deadline的话，那检查一下当前任务耗时是否不比任何一次之前进行的任务都大，如果不是的话加进来，并把之前那个最大的扔出去；否则凉拌。。。（由于N<=150000，所以建议用大根堆维护，本萌妹还是继续用我萌萌哒左偏树，mua~~）
var
i,j,k,m,n,head:longint;
l:int64;
a,lef,rig,fix,b,c,d:array[..] of longint;
function min(x,y:longint):longint;inline;
begin
if x<y then min:=x else min:=y;
end;
function max(x,y:longint):longint;inline;
begin
if x>y then max:=x else max:=y;
end;
procedure swap(var x,y:longint);inline;
var z:longint;
begin
z:=x;x:=y;y:=z;
end;
procedure sort(l,r:longint);inline;
var i,j,x,y:longint;
begin
i:=l;j:=r;
x:=c[(i+j) div ];
repeat
while c[i]<x do inc(i);
while c[j]>x do dec(j);
if i<=j then
begin
swap(c[i],c[j]);
swap(d[i],d[j]);
inc(i);dec(j);
end;
until i>j;
if l<j then sort(l,j);
if i<r then sort(i,r);
end;
procedure merge(var x,y:longint);inline;
begin
if x= then swap(x,y);
if y= then exit;
if a[x]<a[y] then swap(x,y);
merge(rig[x],y);
fix[x]:=max(fix[lef[x]],fix[rig[x]])+;
if fix[lef[x]]<fix[rig[x]] then swap(lef[x],rig[x]);
end;
procedure cuthead(var head:longint);inline;
begin
if head= then exit;
merge(lef[head],rig[head]);
head:=lef[head];
end;
begin
readln(n);
for i:= to n do readln(d[i],c[i]);
sort(,n);l:=;
head:=;m:=;k:=;
fillchar(a,sizeof(a),);
fillchar(lef,sizeof(lef),);
fillchar(rig,sizeof(rig),);
fillchar(fix,sizeof(fix),);
for i:= to n do
begin
if int64(l+int64(d[i]))<=int64(c[i]) then
begin
l:=int64(l+int64(d[i]));inc(k);
inc(m);a[m]:=d[i];
j:=m;merge(head,j);
end
else
begin
if (int64(d[i])<int64(a[head])) then
begin
l:=int64(l+int64(d[i])-int64(a[head]));
inc(m);a[m]:=d[i];
cuthead(head);j:=m;
merge(head,j);
end;
end;
end;
writeln(k);
readln;
end.
var
i,j,k,m,n,head:longint;
l:int64;
a,lef,rig,fix,b,c,d:array[..] of longint;
function min(x,y:longint):longint;inline;
begin
if x<y then min:=x else min:=y;
end;
function max(x,y:longint):longint;inline;
begin
if x>y then max:=x else max:=y;
end;
procedure swap(var x,y:longint);inline;
var z:longint;
begin
z:=x;x:=y;y:=z;
end;
procedure sort(l,r:longint);inline;
var i,j,x,y:longint;
begin
i:=l;j:=r;
x:=c[(i+j) div ];
repeat
while c[i]<x do inc(i);
while c[j]>x do dec(j);
if i<=j then
begin
swap(c[i],c[j]);
swap(d[i],d[j]);
inc(i);dec(j);
end;
until i>j;
if l<j then sort(l,j);
if i<r then sort(i,r);
end;
procedure merge(var x,y:longint);inline;
begin
if x= then swap(x,y);
if y= then exit;
if a[x]<a[y] then swap(x,y);
merge(rig[x],y);
fix[x]:=max(fix[lef[x]],fix[rig[x]])+;
if fix[lef[x]]<fix[rig[x]] then swap(lef[x],rig[x]);
end;
procedure cuthead(var head:longint);inline;
begin
if head= then exit;
merge(lef[head],rig[head]);
head:=lef[head];
end;
begin
readln(n);
for i:= to n do readln(d[i],c[i]);
sort(,n);l:=;
head:=;m:=;k:=;
fillchar(a,sizeof(a),);
fillchar(lef,sizeof(lef),);
fillchar(rig,sizeof(rig),);
fillchar(fix,sizeof(fix),);
for i:= to n do
begin
if int64(l+int64(d[i]))<=int64(c[i]) then
begin
l:=int64(l+int64(d[i]));inc(k);
inc(m);a[m]:=d[i];
j:=m;merge(head,j);
end
else
begin
if (int64(d[i])<int64(a[head])) then
begin
l:=int64(l+int64(d[i])-int64(a[head]));
inc(m);a[m]:=d[i];
cuthead(head);j:=m;
merge(head,j);
end;
end;
end;
writeln(k);
readln;
end.
