NOIP2011普及组 瑞士环 保序性

题目链接：http://noi.openjudge.cn/ch0401/4363/

分析：如果直接模拟，时间复杂度是O（r*nlogn)超时

然后我们发现每次一轮开始时，刚开始是保序的，然后我们可以把所有赢得人拿出来，输的人也拿出来

发现赢得人还是保序的，输的人也是保序的，所以最终我们要干的就是把两个保序的序列合成一个保序的的序列

这样只需要排序一次，时间发杂度O（nlogn+r*n)可过

#include <iostream>

#include <string.h>

#include <algorithm>

#include <stdio.h>

#include <vector>

#include <math.h>

using namespace std;

typedef long long LL;

const int INF=0x3f3f3f3f;

const int N=2e5+;

int w[N],v[N],id[N];

int a[N>>],b[N>>];

bool cmp(int x,int y){

  if(v[x]==v[y])return x>y;

  return v[x]<v[y];

}

int main()

{

    int n,r,q;

    scanf("%d%d%d",&n,&r,&q);

    n<<=;

    for(int i=;i<=n;++i)

     scanf("%d",&v[i]),id[i]=i;

    for(int i=;i<=n;++i)

     scanf("%d",&w[i]);

    sort(id+,id++n,cmp);

    for(int i=;i<=r;++i){

      int cnt=;

      for(int i=;i<=n;i+=){

        if(w[id[i]]<w[id[i+]]){

          --v[id[i]];

          ++cnt;

          a[cnt]=id[i];

          b[cnt]=id[i+];

        }

        else{

          --v[id[i+]];

          ++cnt;

          a[cnt]=id[i+];

          b[cnt]=id[i];

        }

      }

      int pos1=,pos2=,l=n/;

      for(int i=;i<=n;++i){

        if(pos1>l)id[i]=b[pos2++];

        else if(pos2>l)id[i]=a[pos1++];

        else{

           if(v[a[pos1]]<v[b[pos2]])

             id[i]=a[pos1++];

           else if(v[a[pos1]]>v[b[pos2]])

             id[i]=b[pos2++];

           else{

             if(a[pos1]<b[pos2])

              id[i]=b[pos2++];

             else

              id[i]=a[pos1++];

           }

        }

      }

    }

    printf("%d\n",id[n-q+]);

    return ;

}