NOIP2011瑞士轮

Answer 1

　　我觉得应该先快排， 加代码：
　　type re=record
　　s:longint;
　　w:longint;
　　num:longint;
　　end;
　　var n,n1,r,q,i,j,x,y,p,c:longint;
　　t:re;
　　f:array[0..1,0..1000000]of re;
　　procedure qsort(l,r:longint);
　　var i,j:longint;
　　w:re;
　　begin
　　i:=l;
　　j:=r;
　　w:=f[1,(l+r)div 2];
　　while(i<=j)do
　　begin
　　while( (f[1,i].s>w.s) or ((f[1,i].s=w.s) and (f[1,i].num<w.num) ) )do
　　inc(i);
　　while( (f[1,j].s<w.s) or ((f[1,j].s=w.s) and (f[1,j].num>w.num) ) )do
　　dec(j);
　　if i<=j then begin
　　t:=f[1,i];
　　f[1,i]:=f[1,j];
　　f[1,j]:=t;
　　inc(i);
　　dec(j);
　　end;
　　end;
　　if i<r then
　　qsort(i,r);
　　if j>l then
　　qsort(l,j);
　　end;
　　begin
　　readln(n,r,q);
　　n1:=n;
　　n:=n*2;
　　for i:=1 to n do read(f[1,i].s);
　　for i:=1 to n do
　　begin
　　read(f[1,i].w);
　　f[1,i].num:=i;
　　end;
　　c:=1;
　　qsort(1,n);
　　for p:=1 to r do
　　begin
　　for i:=1 to n1 do
　　begin
　　if f[c,i*2-1].w<f[c,i*2].w then
　　begin
　　inc(f[c,i*2].s);
　　t:=f[c,i*2-1];
　　f[c,i*2-1]:=f[c,i*2];
　　f[c,i*2]:=t;
　　end
　　else
　　inc(f[c,i*2-1].s);
　　end;
　　x:=1;
　　y:=2;
　　for i:=1 to n do
　　begin
　　if (x<n)and((f[c,x].s>f[c,y].s) or
　　((f[c,x].s=f[c,y].s)and(f[c,x].num<f[c,y].num))) then
　　begin
　　f[1-c,i]:=f[c,x];
　　inc(x,2);
　　end
　　else
　　begin
　　f[1-c,i]:=f[c,y];
　　inc(y,2);
　　end;
　　end;
　　c:=1-c;
　　end;
　　writeln(f[c,q].num);
　　end.

Answer 2

归并排序。
胜的分一组是有序的，败的分一组也是有序的。
归并O（n）。

参考资料：http://zhidao.baidu.com/question/352975637.html