毕业季•友

   
“友谊的小船是如何看头?友谊是一种很玄很玄的事物,它能够忍受诱惑也坚韧不破,但也得以因为鸡毛蒜皮说翻就翻。”

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

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

Description

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

宗旨中介绍的瑞士联邦轮比赛制度,因最早选取于1895年在瑞士联邦开设的国际象棋竞技而得名。它能够用作是淘汰赛与循环赛的妥胁,既保障了竞技的八面玲珑,又能使比赛日程不至于过长。
2*N 名编号为 1~2N
的运动员共进行RAV4轮比赛。每轮比赛初始前,以及有着比赛甘休后,都会遵从总分从高到低对运动员进行3次排行。选手的总分为率先轮开始前的初阶分数加桐月参加过的拥有比赛的得分和。总分一样的,约定编号较小的运动员排行靠前。

每轮比赛的势不两立布署与该轮竞技早先前的排行有关:第壹 名和第三 名、第 3
名和第 4名、……、第3K – 1 名和第 2K名、…… 、第1N – 1
名和第③N名,各进行一场交锋。每场竞技胜者得1 分,负者得 0
分。相当于说除了第一批次以外,别的轮交锋的安插均不能够事先分明,而是要在于选手在头里交锋中的表现。

现给定每一种选手的上马分数及其实力值,试计算在ENVISION 轮竞赛过后,排行第 Q
的选手编号是稍稍。我们假如选手的实力值两两分歧,且每场比赛后实力值较高的总能赢球。

   
三年前的那个时候,劳碌着复试,踏上了往来首都的路,而便是那条路,让本人在三年的时日里,收获了越来越多。

Input

输入的第贰行是多少个正整数N、奥迪Q5 、Q,每七个数里面用多个空格隔开分离,表示有
2*N 名运动员、Sportage 轮比赛,以及大家关切的排行 Q。

第叁行是2N 个非负整数s1, s2, …, s2N,每八个数里面用叁个空格隔离,当中si 表示编号为i 的运动员的始发分数。 第2行是2N 个正整数w1 , w2 , …,
w2N,每四个数以内用3个空格隔断,当中 wi 表示编号为i 的运动员的实力值。

 

Output

出口唯有一行,包罗2个整数,即安德拉 轮竞赛甘休后,排名第 Q 的运动员的编号。

   
进驻北京邮政和邮电通讯高校,可谓是1个新的初叶,在那边,小编的高级中学型小型伙伴们、本科小伙伴们以及硕士小伙伴们,带给了自笔者太多太多的尊敬,由衷地谢谢亲们,能够让作者在四个面生的地方,享受家的浓香。

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

图片 1 

Source

分治,归并排序

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

缓解思路

刚看那道难题一定想到的是每一轮都全体以分数为第2重庆大学字、编号为第贰根本字排序3遍,但如此必然会晚点,所以大家另寻办法。

因为每三遍竞技中胜者的分数都只+1,所以一旦大家在每一轮过后把胜者和败者分别放入多个数组,大家会发觉,它们分别都以严守原地的。

之所以为了采纳好这些脾气,我们选用归并排序,这样就不会爆时间了。

 图片 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;
}

   
记得在研一初入北京邮政和邮电通信高校时,曾吟诗感慨:“善语怀心种邮田,千里群聚是谓缘。”有了那层缘分,就尘埃落定了那群朋友,从目生到熟习,从了然到交心,一步一步,我们聚到了那边。就是你们,那两年半的硕士,才会多姿多彩;便是你们,那苦逼的实验室岁月才充满开心;就是你们,作者,于北京邮政和邮电通信大学,才有了存在过的价值。 

 图片 3图片 4图片 5

   
完成学业了,现在的大家兴许不在八个高校,也许分散外市,也许各自忙绿,但不管如何,要记得,Friend
, Forever!友谊的小艇说翻也不翻!\(^o^)/~

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

 

                                                                                                                                  
——午后·苏风雪

                                                                       
                                                     
二零一四年二月13日周四