P1309 [NOIP 2011 普及組] 瑞士輪

題目背景

在雙人對決的競技性比賽，如乒乓球、羽毛球、國際象棋中，最常見的賽制是淘汰賽和循環賽。前者的特點是比賽場數少，每場都緊張刺激，但偶然性較高。后者的特點是較為公平，偶然性較低，但比賽過程往往十分冗長。

本題中介紹的瑞士輪賽制，因最早使用于 1895 年在瑞士舉辦的國際象棋比賽而得名。它可以看作是淘汰賽與循環賽的折中，既保證了比賽的穩定性，又能使賽程不至于過長。

題目描述

\(2 \times N\) 名編號為 \(1\sim 2\times N\) 的選手共進行 \(R\) 輪比賽。每輪比賽開始前，以及所有比賽結束后，都會按照總分從高到低對選手進行一次排名。選手的總分為第一輪開始前的初始分數加上已參加過的所有比賽的得分和。總分相同的，約定編號較小的選手排名靠前。

每輪比賽的對陣安排與該輪比賽開始前的排名有關：第 \(1\) 名和第 \(2\) 名、第 \(3\) 名和第 \(4\) 名、……、第 $2\times K - 1 $ 名和第 \(2\times K\) 名、…… 、第 \(2\times N - 1\) 名和第 \(2\times N\) 名，各進行一場比賽。每場比賽勝者得 \(1\) 分，負者得 \(0\) 分。也就是說除了首輪以外，其它輪比賽的安排均不能事先確定，而是要取決于選手在之前比賽中的表現。

現給定每個選手的初始分數及其實力值，試計算在 \(R\) 輪比賽過后，排名第 \(Q\) 的選手編號是多少。我們假設選手的實力值兩兩不同，且每場比賽中實力值較高的總能獲勝。

輸入格式

第一行是三個正整數 \(N,R,Q\)，每兩個數之間用一個空格隔開，表示有 $2\times N $ 名選手、\(R\) 輪比賽，以及我們關心的名次 \(Q\)。

第二行是 \(2\times N\) 個非負整數 \(s_1, s_2,\dots, s_{2\times N}\)，每兩個數之間用一個空格隔開，其中 $s_i $ 表示編號為 \(i\) 的選手的初始分數。

第三行是 \(2\times N\) 個正整數 \(w_1,w_2,\dots,w_{2\times N}\)，每兩個數之間用一個空格隔開，其中 \(w_i\) 表示編號為 \(i\) 的選手的實力值。

輸出格式

一個整數，即 \(R\) 輪比賽結束后，排名第 \(Q\) 的選手的編號。

輸入輸出樣例 #1

輸入 #1

2 4 2 
7 6 6 7 
10 5 20 15

輸出 #1

1

說明/提示

【樣例解釋】

【數據范圍】

對于 \(30\%\) 的數據，\(1\le N\le 100\)；

對于 \(50\%\) 的數據，\(1\le N\le 10000\)；

對于 \(100\%\) 的數據，\(1\le N\le 10^5,1\le R\le 50,1\le Q\le 2\times N,0\le s_1, s_2,\dots,s_{2\times N}\le 10^8,1\le w_1, w_2 , \dots, w_{2\times N}\le 10^8\)。

noip2011 普及組第 3 題。

AC代碼

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct st
{
    int id, gra, sh;
};

bool cmp(const st &a, const st &b)
{
    if (a.gra != b.gra)
        return a.gra > b.gra;
    return a.id < b.id;
}

void mergeMatches(vector<st> &players)
{
    int n = players.size() / 2;
    vector<st> winners, losers;

    for (int i = 0; i < 2 * n; i += 2)
    {
        if (players[i].sh > players[i + 1].sh)
        {
            players[i].gra++;
            winners.push_back(players[i]);
            losers.push_back(players[i + 1]);
        }
        else
        {
            players[i + 1].gra++;
            winners.push_back(players[i + 1]);
            losers.push_back(players[i]);
        }
    }

    players.clear();
    int i = 0, j = 0;
    while (i < winners.size() && j < losers.size())
    {
        if (cmp(winners[i], losers[j]))
        {
            players.push_back(winners[i++]);
        }
        else
        {
            players.push_back(losers[j++]);
        }
    }
    while (i < winners.size())
        players.push_back(winners[i++]);
    while (j < losers.size())
        players.push_back(losers[j++]);
}

int main()
{
    int N, R, Q;
    cin >> N >> R >> Q;

    vector<st> players(2 * N);
    for (int i = 0; i < 2 * N; i++)
    {
        players[i].id = i + 1;
        cin >> players[i].gra;
    }
    for (int i = 0; i < 2 * N; i++)
    {
        cin >> players[i].sh;
    }

    // 初始排序
    sort(players.begin(), players.end(), cmp);

    // 進行R輪比賽
    for (int round = 0; round < R; round++)
    {
        mergeMatches(players);
    }

    cout << players[Q - 1].id << endl;
    return 0;
}