洛谷 P1309 瑞士轮

题目链接：https://www.luogu.org/problemnew/show/P1309

题目背景

在双人对决的竞技性比赛，如乒乓球、羽毛球、国际象棋中，最常见的赛制是淘汰赛和循环赛。前者的特点是比赛场数少，每场都紧张刺激，但偶然性较高。后者的特点是较为公平，偶然性较低，但比赛过程往往十分冗长。

本题中介绍的瑞士轮赛制，因最早使用于

题目描述

每轮比赛的对阵安排与该轮比赛开始前的排名有关：第

现给定每个选手的初始分数及其实力值，试计算在R 轮比赛过后，排名第

输入输出格式

输入格式：

第一行是三个正整数

第二行是 $s_1, s_2, …, s_{2N}s1,s2,…,s2N ，每两个数之间用一个空格隔开，其中 s_isi 表示编号为 ii 的选手的初始分数。第三行是 2 imes N2×N 个正整数 w_1 , w_2 , …, w_{2N}w1,w2,…,w2N ，每两个数之间用一个空格隔开，其中 w_iwi 表示编号为 ii的选手的实力值。$

输出格式：

一个整数，即

输入输出样例

输入样例#1：

2 4 2 
7 6 6 7 
10 5 20 15

输出样例#1：

说明

【样例解释】

【数据范围】

对于 $30\%30% 的数据， 1 ≤ N ≤ 1001≤N≤100 ；$

对于 $50\%50% 的数据， 1 ≤ N ≤ 10,0001≤N≤10,000 ；$

对于 $100\%100% 的数据， 1 ≤ N ≤ 100,000,1 ≤ R ≤ 50,1 ≤ Q ≤ 2N,0 ≤ s_1, s_2, …, s_{2N}≤10^8,1 ≤w_1, w_2 , …, w_{2N}≤ 10^81≤N≤100,000,1≤R≤50,1≤Q≤2N,0≤s1,s2,…,s2N≤108,1≤w1,w2,…,w2N≤108。$

分析

#include<bits/stdc++.h>
using namespace std;
long long n,r,q;//2*n人，r轮比赛，q为目标名次
struct competitor
{
    long long power;
    long long point;
    long long num;
};
competitor a[200005],win[200005],lost[200005];
long long kwin,klost;
bool cmp(competitor c,competitor b)
{
    if(c.point==b.point) return c.num<b.num;
    else return c.point>b.point;
}
int main()
{
    cin>>n
    >>r
    >>q;
    n=2*n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i].point;
        a[i].num=i+1;
    }
    for(int i=0;i<n;i++)
    {
        cin>>a[i].power;
    }
    sort(a+0,a+n,cmp);
    while(r--)
    {
        for(int i=0;i<n-1;i=i+2)
        {
            if(a[i].power>a[i+1].power) 
            {
                a[i].point++;
                win[kwin]=a[i];
                lost[klost]=a[i+1];
                klost++;
                kwin++;
            }
            else 
            {
                a[i+1].point++;
                win[kwin]=a[i+1];
                lost[klost]=a[i];
                klost++;
                kwin++;
            }
        }//之前已经排好序，所以将+1的序列放到一起，将-1的序列放到一起，两者仍然排好序。 
        merge(win+0,win+kwin,lost+0,lost+klost,a,cmp);
        klost=0;
        kwin=0;
    }
    cout<<a[q-1].num<<endl;
    return 0;
}