P1309 瑞士轮

啊，时间过得好快

学了1年编程，就从普及组退役了 //(ㄒoㄒ)//

还有200天就要参加恐怖的noip提高组 //(ㄒoㄒ)//

今天开始正式备战2019noip-TG

发两篇题解，记录我此时的水平

分别是

棋盘（2017noip-PJ-T3）

瑞士轮（就是这篇）（2011noip-PJ-T3）

maybe，我水平不止这点

这只说明了noip-PJ我只能AK前三道（自动过滤摆渡车）

---

以上纯属瞎扯，您可以从这儿开始看

原题链接

这道题看上起简单

BUT！！！

 如果用快拍

O=N*logN*R

logN ≈20

∴O≈1,000,000,000

对于1000ms

会TLE

---

这里很重要的一点是

每一局win的人彼此之间  以及  fail的人彼此之间的排名是不变的

这就是这道题用归并的原因

准确地说

这只是归并排序的思想

排序两个有序序列的方法

代码见下^_^

#include<bits/stdc++.h>
using namespace std;
struct node{
    int x,num,shili;//得分,编号,实力 
};
node a[2000050];
node win[1000050]; 
node fail[1000050];
int n,r,q,i;
bool cmp(node a,node b)
{
    if(a.x!=b.x)
    return a.x>b.x;
    else 
    return a.num<b.num;
}
void m_sort()//归并 
{//准确的说，是合并的操作 
    int i=1,j=1,k=1;
    while(i<=n && j<=n)
    {
        if(cmp(win[i],fail[j]))
        {
            a[k]=win[i];
            i++;k++;
        }
        else
        {
            a[k]=fail[j];
            j++;k++;
        }
    }
    while(i<=n)
    {
        a[k]=win[i];
        i++;k++;
    }
    while(j<=n)
    {
        a[k]=fail[j];
        j++;k++;
    }
}
int main()
{
    cin>>n>>r>>q;
    for(i=1;i<=n*2;i++)
    {
        cin>>a[i].x;
        a[i].num=i;
    } 
    for(i=1;i<=n*2;i++)
    cin>>a[i].shili;
    sort(a+1,a+1+n*2,cmp);//初始进行排名 
    while(r--)
    {
      for(int i=1;i<=n;i++)
      {
          if(a[i*2-1].shili>a[i*2].shili)
          {
              a[i*2-1].x++;
              win[i]=a[i*2-1];
              fail[i]=a[i*2];
          }
          else
          {
              a[i*2].x++;
              win[i]=a[i*2];
              fail[i]=a[i*2-1];
          }
       }    
       m_sort();
    }
    cout<<a[q].num;
    return 0;
}