洛谷1309 瑞士轮 解题报告

洛谷1309 瑞士轮

本题地址： http://www.luogu.org/problem/show?pid=1309

题目背景

　　在双人对决的竞技性比赛，如乒乓球、羽毛球、国际象棋中，最常见的赛制是淘汰赛和循环赛。前者的特点是比赛场数少，每场都紧张刺激，但偶然性较高。后者的特点是较为公平，偶然性较低，但比赛过程往往十分冗长。 　　本题中介绍的瑞士轮赛制，因最早使用于1895年在瑞士举办的国际象棋比赛而得名。它可以看作是淘汰赛与循环赛的折衷，既保证了比赛的稳定性，又能使赛程不至于过长。

题目描述

　　2*N 名编号为 1~2N 的选手共进行R 轮比赛。每轮比赛开始前，以及所有比赛结束后，都会按照总分从高到低对选手进行一次排名。选手的总分为第一轮开始前的初始分数加上已参加过的所有比赛的得分和。总分相同的，约定编号较小的选手排名靠前。 
　　每轮比赛的对阵安排与该轮比赛开始前的排名有关：第1 名和第2 名、第 3 名和第 4名、……、第2K – 1 名和第 2K名、……  、第2N – 1 名和第2N名，各进行一场比赛。每场比赛胜者得1 分，负者得 0 分。也就是说除了首轮以外，其它轮比赛的安排均不能事先确定，而是要取决于选手在之前比赛中的表现。 
　　现给定每个选手的初始分数及其实力值，试计算在R 轮比赛过后，排名第 Q 的选手编号是多少。我们假设选手的实力值两两不同，且每场比赛中实力值较高的总能获胜。

输入输出格式

输入格式：

输入文件名为swiss.in 。 
　　输入的第一行是三个正整数N、R 、Q，每两个数之间用一个空格隔开，表示有 2*N 名选手、R 轮比赛，以及我们关心的名次 Q。 
　　第二行是2*N 个非负整数s1, s2, …, s2N，每两个数之间用一个空格隔开，其中 si 表示编号为i 的选手的初始分数。 第三行是2*N 个正整数w1 , w2 , …, w2N，每两个数之间用一个空格隔开，其中 wi 表示编号为i 的选手的实力值。

输出格式：

　　输出文件名为swiss.out。 
　　输出只有一行，包含一个整数，即R 轮比赛结束后，排名第 Q 的选手的编号。

输入输出样例

输入样例#1：

2 4 2 
7 6 6 7 
10 5 20 15

输出样例#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。 
noip2011普及组第3题。

题解

模拟+排序

这道题用朴素做法会超时，我们可以采用这样的做法。

比赛用模拟的方法进行排序。

考虑到每个人的名次变动是有限的，对于所有在当前局比赛击败对手的人，他们的相对次序是不变的。

同样，对于所有在当前局比赛输给对手的人，他们的相对次序也是不变的。

所以我们可以用两个队列保存赢和输的人，能够实现当局比赛O(n)的排序，即可在规定时间出解。

下面附上代码。

代码

  1. var i1,i2,x,k,i,j,n,q,r,t,y,kmax,kmin,max,min:longint;      
  2.   b,num,num1,v,a:array[1..200000] of longint;      
  3.       
  4. procedure sort(l,r: longint);      
  5.       var      
  6.          i,j,x,y,x1: longint;      
  7.       begin      
  8.          i:=l;      
  9.          j:=r;      
  10.          x:=a[(l+r) div 2];      
  11.          x1:=num[(l+r) div 2];        
  12.          repeat      
  13.            while (a[i]>x) or (a[i]=x) and (num[i]<x1) do        
  14.             inc(i);      
  15.            while (x>a[j]) or (a[j]=x) and (num[j]>x1) do       
  16.             dec(j);      
  17.            if not(i>j) then      
  18.              begin        
  19.                 y:=v[i];      
  20.                 v[i]:=v[j];      
  21.                 v[j]:=y;      
  22.                 y:=a[i];      
  23.                 a[i]:=a[j];      
  24.                 a[j]:=y;
  25.                 y:=num[i];          
  26.                 num[i]:=num[j];      
  27.                 num[j]:=y;      
  28.                 inc(i);      
  29.                 j:=j-1;      
  30.              end;      
  31.          until i>j;      
  32.          if l<j then      
  33.            sort(l,j);      
  34.          if i<r then      
  35.            sort(i,r);      
  36.       end;      
  37.       
  38. begin      
  39. readln(n,r,q);      
  40. for i:=1 to 2*n do      
  41.  begin      
  42.   read(a[i]);      
  43.   num[i]:=i;      
  44.  end;      
  45. readln;      
  46. sort(1,2*n);        
  47. for i:=1 to 2*n do read(v[i]);      
  48. for i:=1 to r do        
  49.  begin      
  50.       i1:=0; i2:=n;  
  51.     for j:=1 to n do      
  52.      begin      
  53.       if  v[num[j*2-1]]>v[num[j*2]] then  begin  max:=a[j*2-1]; min:=a[j*2];      
  54.                                                   kmax:=j*2-1; kmin:=j*2      
  55.                                            end      
  56.                                     else  begin  max:=a[j*2]; min:=a[j*2-1];      
  57.                                                   kmax:=j*2; kmin:=j*2-1;      
  58.                                              end;      
  59.                  inc(i1);   
  60.                  b[i1]:=max+1; num1[i1]:=num[kmax];      
  61.                  inc(i2);      
  62.                  b[i2]:=min;   num1[i2]:=num[kmin];      
  63.          end;      
  64.         x:=1;  y:=n+1;  k:=0;    
  65.       while (x<=n) and (y<=2*n) do      
  66.        begin      
  67.               if (b[x]>b[y]) or (b[x]=b[y]) and (num1[x]<num1[y]) then 
  68.                 begin
  69.                   inc(k);      
  70.                   a[k]:=b[x];      
  71.                   num[k]:=num1[x];      
  72.                   inc(x);      
  73.                 end      
  74.               else begin inc(k);  a[k]:=b[y]; num[k]:=num1[y]; inc(y); end;      
  75.        end;      
  76.       if x<=n  then  for j:=x to n do  begin   inc(k);a[k]:=b[j]; num[k]:=num1[j] end;      
  77.       if y<=2*n then for j:=y to 2*n do begin inc(k);  a[k]:=b[j]; num[k]:=num1[j];  end;      
  78.  end;      
  79. writeln(num[q]);      
  80. end.    

（本文系笔者原创，未经允许不得转载）

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/yzm10/p/4751367.html