Luogu1309 瑞士联邦轮(分治,归并排序)

   
“友谊的小艇是怎么着意思?友谊是一种很玄很玄的事物,它能够忍受诱惑也坚韧不破,但也足以因为鸡毛蒜皮说翻就翻。”

Luogu1309 瑞士联邦轮(分治,归并排序)

                                                                                                                                  
——“友谊的小艇说翻就翻”

Description

在双人对决的竞赛性比赛,如斯诺克、羽球、国际象棋中,最广泛的比赛制度是淘汰赛和循环赛。前者的风味是竞赛场数少,每场都紧张刺激,但偶然性较高。后者的性状是较为公平,偶然性较低,但比赛进度反复拾叁分冗长。

核心中牵线的瑞士轮比赛制度,因最早选用于1895年在瑞士开设的国际象棋比赛而得名。它能够看成是淘汰赛与循环赛的折衷,既保障了比赛的平稳,又能使比赛日程不至于过长。
2*N 名编号为 1~2N
的健儿共实行Sportage轮比赛。每轮比赛开头前,以及独具比赛截止后,都会依据总分从高到低对运动员举行二回排行。选手的总分为首轮开头前的早先分数加蚕月在场过的享有竞赛的得分和。总分一样的,约定编号较小的健儿排名靠前。

每轮比赛的对立布置与该轮比赛开头前的排名有关:第① 名和第① 名、第 3
名和第 4名、……、第2K – 1 名和第 2K名、…… 、第3N – 1
名和第三N名,各举办一场竞技。每场比赛胜者得1 分,负者得 0
分。也正是说除了第一批次以外,别的轮竞技的安插均无法事先分明,而是要取决于选手在以前交锋中的表现。

现给定各样选手的启幕分数及其实力值,试总计在大切诺基 轮竞赛过后,排名第 Q
的健儿编号是有个别。大家只要选手的实力值两两区别,且每场竞技前实力值较高的总能赢球。

   
三年前的那么些时候,艰巨着复试,踏上了来回香港的路,而正是那条路,让本人在三年的岁月里,收获了更加多。

Input

输入的第三行是多个正整数N、帕杰罗 、Q,每三个数以内用2个空格隔断,表示有
2*N 名运动员、Highlander 轮比赛,以及大家关心的排行 Q。

其次行是2N 个非负整数s1, s2, …, s2N,每八个数以内用三个空格隔开分离,个中si 表示编号为i 的健儿的发端分数。 第一行是2N 个正整数w1 , w2 , …,
w2N,每五个数以内用3个空格隔断,个中 wi 表示编号为i 的健儿的实力值。

 

Output

出口唯有一行,包含1个平头,即哈弗 轮竞技甘休后,排行第 Q 的运动员的号子。

   
进驻北邮,可谓是1个新的开头,在此间,小编的高级中学型小型伙伴们、本科小伙伴们以及硕士小伙伴们,带给了自个儿太多太多的关切,由衷地感激亲们,能够让自家在2个生疏的地方,享受家的菲菲。

Sample Input

2 4 2
7 6 6 7
10 5 20 15

 

Sample Output

1

   
锦州一中,是高中永不磨灭的记得,瓜哥徐利,是大家永远的话题。“巍巍武当山高耸蓝天
山下有作者美观的高校”,一中的校歌,如故可以响彻耳畔。来到了北京邮政和邮电通讯大学,比之江城纽伦堡,离你们近了,近了。王大鹏、于小忱,一个居学校之内,五个卧杏坛之畔,还有轩哥,羽毛球多少人组,扑克牌几个人组,撸串吃喝四个人组。刘志江&对象,阿东,张蹬儿,雅观的女子源,依稀记得那多少个喝醉走丢的友爱,也是二到家。还有牛哥、绝明、Angel儿,来过的家斌······《走过高中》,勿忘始终。

Http

Luogu:https://www.luogu.org/problem/show?pid=1309

葡京注册赠送88 1 

Source

分治,归并排序

   
皇家理工科,水路运输湖畔,三年前,笔者与你话别,但不其他却是理工科的福星,奋斗的岁月。自江城北上,北漂数载,脑中却依稀记得海虹前面包车型客车小吃街,记得绿杨村、四季花、原味餐厅,嬉笑打闹过的海三五楼会议室,认真学习过的航海楼,理工科二桥的石楠花。大滨仔,7年相伴,从二个寝四个班2个实验室,亘古不变;阿梅,同班好友,再聚北京邮政和邮电通讯高校,何等缘分;琴,一起走过班长、走过马研,时间恍惚,簌簌七年;亚男、一男、君萌······,一众好友,回首硕士的年华,满满的感动。

消除思路

刚看那道难点一定想到的是每一轮都全部以分数为率先关键字、编号为第②人命关天字排序三遍,但诸如此类必然会晚点,所以我们另寻办法。

因为每一趟比赛前胜者的分数都只+1,所以即使大家在每一轮过后把胜者和败者分别放入八个数组,大家会发现,它们各自都以板上钉钉的。

从而为了选拔好那特个性,咱们采用归并排序,那样就不会爆时间了。

 葡京注册赠送88 2

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

class PEOPLE//定义人的结构体
{
public:
    int point,w,num;
};

bool operator < (PEOPLE a,PEOPLE b)//重载小于运算符,因为要使用STL中的sort
{
    if (a.point==b.point)
        return a.num<b.num;
    else
        return a.point>b.point;
}

const int maxN=1000001;
const int inf=2147483647;

int n,R,Q;
PEOPLE A[maxN*2];//存放所有人
PEOPLE K1[maxN*2];//每轮后临时存放胜者
PEOPLE K2[maxN*2];//临时存放败者

int main()
{
    cin>>n>>R>>Q;
    for (int i=1;i<=n*2;i++)
        cin>>A[i].point;
    for (int i=1;i<=n*2;i++)
        cin>>A[i].w;
    for (int i=1;i<=n*2;i++)
        A[i].num=i;
    sort(&A[1],&A[2*n+1]);//第一轮前用一边快排
    for (int i=1;i<=R;i++)
    {
        for (int j=1;j<=2*n;j=j+2)
        {
            if (A[j].w>A[j+1].w)
            {
                K1[j/2+1]=A[j];//分别放入两个数组
                K2[j/2+1]=A[j+1];
                K1[j/2+1].point++;
            }
            else
            {
                K1[j/2+1]=A[j+1];
                K2[j/2+1]=A[j];
                K1[j/2+1].point++;
            }
        }
        int j1=1,j2=1;
        for (int j=1;j<=2*n;j++)//归并排序
            if ((j2>n)|| ((j1<=n)&&((K1[j1].point>K2[j2].point)||((K1[j1].point==K2[j2].point)&&(K1[j1].num<K2[j2].num))) )     )
            {
                A[j]=K1[j1];
                j1++;
            }
            else
            {
                A[j]=K2[j2];
                j2++;
            }
    }
    cout<<A[Q].num<<endl;
    return 0;
}

   
记得在研一初入北京邮政和邮电通讯学院时,曾吟诗感慨:“善语怀心种邮田,千里群聚是谓缘。”有了那层缘分,就决定了那群朋友,从面生到熟习,从熟识到交心,一步一步,大家聚到了此处。正是你们,那两年半的硕士,才会多姿多彩;就是你们,那苦逼的实验室岁月才充满高兴;就是你们,作者,于北京邮政和邮电通讯大学,才有了留存过的市场总值。 

 葡京注册赠送88 3葡京注册赠送88 4葡京注册赠送88 5

   
毕业了,未来的大家大概不在三个学校,也许分散外省,可能各自困苦,但不管如何,要记得,Friend
, Forever!友谊的小艇说翻也不翻!\(^o^)/~

    爱你们,真的!(抱抱脸(づ。◕‿‿◕。)づ)

葡京注册赠送88, 

                                                                                                                                  
——午后·苏风雪

                                                                       
                                                     
二〇一六年十一月三日周天