P1309 瑞士輪

題目背景

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

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

題目描述

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

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

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

輸入輸出格式

輸入格式：

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

第二行是2×N 個非負整數\(s_1, s_2, …, s_{2N}\) ，每兩個數之間用一個空格隔開，其中\(s_i\),表示編號為\(i\)的選手的初始分數。 第三行是\(2×N\)個正整數\(w_1 , w_2 , …, w_{2N}\)，每兩個數之間用一個空格隔開，其中\(w_i\)表示編號為\(i\)的選手的實力值。

輸出格式：

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

數據范圍

對于30%的數據,\(1≤N≤100\) ；

對于50%的數據，\(1≤N≤10,000\) ；

對于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^8\)

---

一上來估計了一下復雜度看看高性能的標簽，\(O(2*N*Q*log_2(2*N))\)，直接一頓sort上去。。額60分呢。。

抱怨了一下想了一會兒點開了題解。。

注意到勝利的人分數加了只后屬于勝利的人的一方的相對位置不會改變，同理失敗的一方也是。

聯想到歸并排序的合并，我們這時候只需要\(O(N)\)的復雜度就可以重新拍好序了。

---

#include <cstdio> #include <algorithm> const int N=100010; struct node {int num,score,w;bool friend operator <(node n1,node n2){if(n1.score==n2.score) return n1.num<n2.num;return n1.score>n2.score;}bool friend operator >(node n1,node n2){if(n1.score==n2.score) return n1.num<n2.num;return n1.score>n2.score;} }a[N<<1],b[N<<1]; int n,r,q; void merge() {int l1=1,l2=(n>>1)+1,cnt=0;while(l1<=(n>>1)&&l2<=n){if(b[l2]>b[l1])a[++cnt]=b[l2++];elsea[++cnt]=b[l1++];}while(l1<=(n>>1))a[++cnt]=b[l1++];while(l2<=n)a[++cnt]=b[l2++]; } int main() {scanf("%d%d%d",&n,&r,&q);n<<=1;for(int i=1;i<=n;i++){scanf("%d",&a[i].score);a[i].num=i;}for(int i=1;i<=n;i++)scanf("%d",&a[i].w);for(int i=1;i<=r;i++){if(i==1) std::sort(a+1,a+1+n);else merge();int cnt1=0,cnt2=n>>1;for(int j=1;j<=n;j+=2){if(a[j].w>a[j+1].w)a[j].score++,b[++cnt1]=a[j],b[++cnt2]=a[j+1];elsea[j+1].score++,b[++cnt2]=a[j],b[++cnt1]=a[j+1];}}merge();printf("%d\n",a[q].num);return 0; }

---

2018.6.18

轉載于:https://www.cnblogs.com/butterflydew/p/9196679.html

總結

以上是生活随笔為你收集整理的洛谷 P1309 瑞士轮 解题报告的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。