https://jzoj.net/senior/#contest/show/2045/1
这题是一个我不是很熟悉的堆。 首先，堆就是一个完全二叉树，可以把它抽象成这样： 对于对的操作，我们可以用up 和down 来维护 下列是up 和 down。（详解请看本作者的【专题】堆） up：
procedure up(k:longint); begin while(k>1)and(a[k]<a[k div 2])do begin a[0]:=a[k]; a[k]:=a[k div 2]; a[k div 2]:=a[0]; k:=k div 2; end; end;down：
procedure down(x:longint); var y,k:longint; begin while (x*2<=tot)and(a[x]>a[x*2])or(x*2+1<=tot)and(a[x]>a[x*2+1]) do begin y:=x*2; if(y+1<=tot)and(a[y]>a[y+1])then inc(y); k:=a[x]; a[x]:=a[y]; a[y]:=k; x:=y; end; end;我们用样例来演示一下具体操作： 样例是： 4 1 19 2 10 1 20 2 15 输出：35 排序成： 1 19 1 20 2 10 2 15 首先在堆中加入一个19。 然后时间就到了t=1； 我们发现第二个数的时间要比t+1要小了，那就看看堆顶的和它比较，如果可以，就交换。 变成这样。 然后维护下一组，继续t=1； 然后我们发现，下一个是可以的，就把它加入堆中： 再用up维护一下： 然后发现t=3； 下一个不行，于是就用堆顶来维护， 再用down操作维护一下，但是还是同样。 于是最后答案就是堆里的所有元素之和=35；
var a,p,q,r1,r2:array[0..200000]of int64; i,j,n,m,tot:longint; ans,t:int64; procedure up(k:longint); begin while(k>1)and(a[k]<a[k div 2])do begin a[0]:=a[k]; a[k]:=a[k div 2]; a[k div 2]:=a[0]; k:=k div 2; end; end; procedure down(x:longint); var y,k:longint; begin while (x*2<=tot)and(a[x]>a[x*2])or(x*2+1<=tot)and(a[x]>a[x*2+1]) do begin y:=x*2; if(y+1<=tot)and(a[y]>a[y+1])then inc(y); k:=a[x]; a[x]:=a[y]; a[y]:=k; x:=y; end; end; procedure dg(f,e:longint); var m,i,j,k:longint; begin if f=e then exit; m:=(f+e) div 2; dg(f,m); dg(m+1,e); i:=f; j:=m+1; k:=f; while (i<=m) and (j<=e) do begin if p[i]<p[j] then begin r1[k]:=p[i]; r2[k]:=q[i]; inc(i); inc(k); end else begin r1[k]:=p[j]; r2[k]:=q[j]; inc(j); inc(k); end; end; while i<=m do begin r1[k]:=p[i]; r2[k]:=q[i]; inc(i); inc(k); end; while j<=e do begin r1[k]:=p[j]; r2[k]:=q[j]; inc(j); inc(k); end; for i:=f to e do begin p[i]:=r1[i]; q[i]:=r2[i]; end; end; begin assign(input,'1.in');reset(input); readln(n); for i:=1 to n do readln(p[i],q[i]); dg(1,n); t:=0; for i:=1 to n do begin if(q[i]<=0)or(p[i]=0)then continue; if p[i]>t then begin inc(t); inc(tot); a[tot]:=q[i]; up(tot); end else begin if a[1]<q[i] then begin a[1]:=q[i]; down(1); end; end; end; for i:=1 to tot do ans:=ans+a[i]; writeln(ans); end.