【NOIP2014模拟11.6】射击

题目

https://jzoj.net/senior/#contest/show/2045/1

小结

这题是一个我不是很熟悉的堆。
首先，堆就是一个完全二叉树，可以把它抽象成这样：

对于对的操作，我们可以用up 和down 来维护
下列是up 和 down。（详解请看本作者的【专题】堆）
up：

procedure up(k:longint);
beginwhile(k>1)and(a[k]<a[k div 2])dobegina[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);
vary,k:longint;
beginwhile (x*2<=tot)and(a[x]>a[x*2])or(x*2+1<=tot)and(a[x]>a[x*2+1]) dobeginy:=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；

vara,p,q,r1,r2:array[0..200000]of int64;i,j,n,m,tot:longint;ans,t:int64;
procedure up(k:longint);
beginwhile(k>1)and(a[k]<a[k div 2])dobegina[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);
vary,k:longint;
beginwhile (x*2<=tot)and(a[x]>a[x*2])or(x*2+1<=tot)and(a[x]>a[x*2+1]) dobeginy:=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);
varm,i,j,k:longint;
beginif 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) dobeginif p[i]<p[j] thenbeginr1[k]:=p[i];r2[k]:=q[i];inc(i);inc(k);endelsebeginr1[k]:=p[j];r2[k]:=q[j];inc(j);inc(k);end;end;while i<=m dobeginr1[k]:=p[i];r2[k]:=q[i];inc(i);inc(k);end;while j<=e dobeginr1[k]:=p[j];r2[k]:=q[j];inc(j);inc(k);end;for i:=f to e dobeginp[i]:=r1[i];q[i]:=r2[i];end;
end;
beginassign(input,'1.in');reset(input);readln(n);for i:=1 to n doreadln(p[i],q[i]);dg(1,n);t:=0;for i:=1 to n dobeginif(q[i]<=0)or(p[i]=0)then continue;if p[i]>t thenbegininc(t);inc(tot);a[tot]:=q[i];up(tot);endelsebeginif a[1]<q[i] thenbegina[1]:=q[i];down(1);end;end;end;for i:=1 to tot doans:=ans+a[i];writeln(ans);
end.