首页 > 代码库 > 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建筑抢修 (贪心+堆)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。