首页 > 代码库 > JSOI建筑抢修 (贪心+堆)

JSOI建筑抢修 (贪心+堆)

先按照T2从小到大排序,然后进行贪心。

第i个任务能完成的条件是,sigma(T1[j])+T1[i]<=T2[i] ( j 为之前所选的任务)

如果这个任务不能完成,若max(T1[j]) >T1[i]) , 就将i替换为j , 这样可以使所用任务时间减小。

用一个堆维护最大值即可。

Program XJOI2320;const maxn=150008;var a,b,f:array[0..maxn] of longint;    n,i:longint;    sum,num,ans:int64;    procedure sort(l,r: longint);      var         i,j,x,y: longint;      begin         i:=l;         j:=r;         x:=b[(l+r) div 2];         repeat           while b[i]<x do            inc(i);           while x<b[j] do            dec(j);           if not(i>j) then             begin                y:=a[i];                a[i]:=a[j];                a[j]:=y;                y:=b[i];                b[i]:=b[j];                b[j]:=y;                inc(i);                j:=j-1;             end;         until i>j;         if l<j then           sort(l,j);         if i<r then           sort(i,r);      end;procedure swap(a,b:longint);var temp:longint;begin    temp:=f[a]; f[a]:=f[b];f[b]:=temp;end;procedure insert(x:longint);var i:longint;begin    inc(num);    f[num]:=x;    i:=num;    while i>1 do    begin        if f[i]>f[i div 2] then swap(i,i div 2) else break;        i:=i div 2;    end;end;procedure delete(x:longint);var i:longint;begin    f[1]:=f[num];    dec(num);    i:=2;    while i<=num do    begin        if (i+1<=num) and (f[i+1]>f[i]) then inc(i);        if f[i]>f[i div 2] then swap(i,i div 2) else break;        i:=i*2;    end;end;begin    readln(n);    for i:=1 to n do readln(a[i],b[i]);    sort(1,n);    sum:=0; num:=0; ans:=0;    for i:=1 to n do        if sum+a[i]<=b[i] then        begin            inc(ans);            sum:=sum+a[i];            insert(a[i]);        end else        if a[i]<f[1] then        begin            sum:=sum-f[1];            delete(1);            insert(a[i]);            sum:=sum+a[i];        end;        writeln(ans);end.

 

JSOI建筑抢修 (贪心+堆)