[NOIP201一澳门葡京手机网址]瑞士联邦轮

题目:在部分壹对1游戏的比赛(如下棋、乒球和羽球的单打)中,大家平时会遇见A胜过B,B胜过C而C又胜过A的妙趣横生场馆,不要紧形象的称为剪刀石头布情状。有的时候,无聊的大千世界会津津乐道于总结有些许那样的剪子石头布情况时有爆发,即有多少对严节长富组(A,
B,
C),满足当中的壹个人在竞技前赢了另一个人,另壹个人赢了第三个人而第多少人又胜过了第3私人住房。注意那里冬天的情致是说雅士利组兰秋素的逐1并不重要,将(A,
B, C)、(A, C, B)、(B, A, C)、(B, C, A)、(C, A, B)和(C, B,
A)视为等同的景色。
       
N私家加入一场那样的玩耍的竞技,比赛日程规定私自多个人以内都要开始展览一场比赛:那样壹起有场竞赛。比赛壹度展开了一片段,我们想明白在最棒情状下,竞赛截止后最多会产生稍微剪刀石头布意况。即给出已经发出的比赛结果,而你能够自由布署剩下的较量的结果,以得到尽量多的剪子石头布境况。

noip201壹普及组第二题。

解法:那题的图转化很妙。O.O
是个好题,留那唯一的三个坑先……

难题背景

  在双人对决的竞赛性比赛,如斯诺克、羽球、国际象棋中,最广泛的赛制是淘汰赛和循环赛。前者的特征是竞赛场数少,每场都浮动刺激,但偶然性较高。后者的特性是较为公平,偶然性较低,但比赛进度反复十一分冗长。本题中牵线的瑞士联邦轮比赛制度,因最早采纳于18玖5年在瑞士联邦实行的国际象棋竞技而得名。它能够看成是淘汰赛与循环赛的折衷,既保险了比赛的安宁,又能使比赛日程不至于过长。

题材叙述

  2*N 名编号为 一~二N 的运动员共开展ENCORE轮比赛。每轮比赛初步前,以及独具比赛结束后,都会遵从总分从高到低对选手进行三回排名。选手的总分为率先轮初始前的初始分数加暮春参与过的具备竞赛的得分和。总分壹样的,约定编号较小的健儿排行靠前。 
  每轮较量的对立安插与该轮竞赛开首前的排行有关:第1 名和第壹 名、第 叁名和第 四名、……、第3K – 一 名和第 2K名、……  、第三N – 一名和第壹N名,各实行一场比赛。每场竞赛胜者得一 分,负者得 0
分。也正是说除了第一群次以外,别的轮较量的安插均不可能事先分明,而是要在于选手在事先交锋中的表现。 
  现给定每个选手的启幕分数及其实力值,试计算在奥迪Q5 轮竞技过后,排行第 Q
的运动员编号是有个别。大家假设选手的实力值两两不相同,且每场比赛中实力值较高的总能赢球。

输入输出格式

输入格式:

输入文件名字为swiss.in 。 
  输入的首先行是多个正整数N、昂科拉 、Q,每四个数以内用多少个空格隔离,表示有
二*N 名运动员、昂科威 轮竞技,以及大家关怀的排名 Q。 
  第3行是二*N 个非负整数s1, s二, …,
s贰N,每七个数以内用1个空格隔开分离,当中 si 表示编号为i 的健儿的开首分数。
第二行是2*N 个正整数w一 , w二 , …, w二N,每五个数以内用一个空格隔断,在这之中wi 表示编号为i 的运动员的实力值。

输出格式:

  输出文件名称叫swiss.out。 
  输出只有一行,包涵2个整数,即景逸SUV 轮竞技甘休后,排行第 Q
的运动员的号码。

输入输出样例

输入样例#1:

2 4 2 
7 6 6 7 
10 5 20 15 

出口样例#1:

1

说明

【样例解释】
澳门葡京手机网址 1
【数据范围】 
对于30% 的数据,1 ≤ N ≤ 100; 
对于50% 的数据,1 ≤ N ≤ 10,000 ;

 对于100%的数据,1 ≤ N ≤ 100,000,1 ≤ R ≤ 50,1 ≤ Q ≤ 2N,0 ≤ s1, s2, …,
s2N≤10^8,1 ≤w1, w2 , …, w2N≤ 10^8。 

思路

  若是用极快排序的话只好过八分之四的数额,此题的正解是快排加归并。首先火速排序作为开端状态,然后模拟选出每场竞技的优胜者和战败者,优胜者每人加上壹分后排行不变。所以再用归并排序合并多个有序数组。(PS:此归并非二分归并,能够参考一下以此题,{http://codevs.cn/problem/3296/},用指针实现即可)时间复杂度O(RN)。

  PS:作者居然让如此四个普及组的水题坑了一天,代码已经上涨到200多行,后来竟是是神速排序时的一片段操作未有设想和变量的难题。

澳门葡京手机网址 2澳门葡京手机网址 3

type ss=record
    fen,shi,hao:int64;
    end;

type arr=array[0..200000] of ss;

var a,b,c:arr;
    n,r,q:int64;
    ii:longint;

procedure sort(l,r: longint);
      var
         i,j,x,y: longint;
      begin
         i:=l;
         j:=r;
         x:=a[(l+r) div 2].fen;
         y:=a[(l+r) div 2].hao;
         repeat
           while (a[i].fen>x) or ((x=a[i].fen) and (y>a[i].hao))do
            inc(i);
           while (x>a[j].fen) or ((x=a[j].fen) and (y<a[j].hao)) do
            dec(j);
           if not(i>j) then
             begin
                a[0]:=a[i];
                a[i]:=a[j];
                a[j]:=a[0];
                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 guibing;
var i,j,k:int64;x:longint;
begin
    fillchar(a,sizeof(a),0);
    i:=1;
    j:=1;
    k:=1;
    while (i<>n+1)and(j<>n+1) do
        begin
            if b[i].fen>c[j].fen then
                begin
                    a[k]:=b[i];
                    inc(i);
                    inc(k);
                end;
            if c[j].fen>b[i].fen then
                begin
                    a[k]:=c[j];
                    inc(j);
                    inc(k);
                end;
            if c[j].fen=b[i].fen then
                if c[j].hao<b[i].hao then
                    begin
                        a[k]:=c[j];
                        inc(j);
                        inc(k);
                    end
                else
                    begin
                        a[k]:=b[i];
                        inc(i);
                        inc(k);
                    end;
        end;
    for x:=i to n do
            begin
                a[k]:=b[x];
                inc(k);
            end;
    for x:=j to n do
            begin
                a[k]:=c[x];
                inc(k);
            end;
end;
//归并排序

procedure init;
var i:longint;
begin
    readln(n,r,q);
    for i:=1 to 2*n do a[i].hao:=i;
    for i:=1 to 2*n do read(a[i].fen);
    for i:=1 to 2*n do read(a[i].shi);
end;

procedure main;
var sum1,sum2:int64;i,j:longint;
begin
    fillchar(b,sizeof(b),0);
    fillchar(c,sizeof(c),0);
    i:=1;
    sum1:=0;
    sum2:=0;
    while i<=2*n do
        begin
            j:=i+1;
            if a[i].shi<a[j].shi then
                begin
                    inc(sum1);
                    inc(sum2);
                    b[sum1]:=a[j];
                    c[sum2]:=a[i];
                    inc(b[sum1].fen);
                end
            else
                begin
                    inc(sum1);
                    inc(sum2);
                    b[sum1]:=a[i];
                    c[sum2]:=a[j];
                    inc(b[sum1].fen);
                end;
            inc(i,2);
        end;
    guibing;
end;
//模拟比赛过程

procedure printf;
var i:longint;
begin
    writeln(a[q].hao);
end;

begin
    init;
    sort(1,2*n);
    for ii:=1 to r do main;
    printf;
end.

View Code