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

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

时间过的真快,恍然之间,自个儿早就进步二十10周岁的秘诀了。从前平素想不亮堂,为何小的时候以为时间过的真慢,每十14日想长大了,能够做家长做的那三个事情,比如不要挨打,比如上班赚钱,比如娶个媳妇等等。近年来那几个都形成了,却认为时间一天比一天过的快,快到甚至有点心惊胆战了,那么多的事务没有做,万一哪天看到马克思了,真不佳交待。直到读了李笑来老师的《把日子作为朋友》那本书(卓绝推荐介绍各位去读下,肯定会有不同等的取得)才驾驭,原来是与经历有关。五岁长到6岁的一年,占去了人生的十分二,而三十周岁到30岁的一年,去只占已走过人生的3%,20:3,那是多大的百分比呀,也难怪觉得how
time flies!

Description

在双人对决的比赛性竞技,如斯诺克、羽球、国际象棋中,最广大的比赛制度是淘汰赛和循环赛。前者的特点是竞比赛场所数少,每场都浮动刺激,但偶然性较高。后者的特色是比较公平,偶然性较低,但竞赛进度往往越发冗长。

核心中介绍的瑞士联邦轮比赛制度,因最早采纳于1895年在瑞士联邦设置的国际象棋比赛而得名。它能够当做是淘汰赛与循环赛的投降,既保险了竞赛的安居乐业,又能使比赛日程不至于过长。
2*N 名编号为 1~2N
的健儿共实行PRADO轮竞赛。每轮竞赛开头前,以及独具比赛甘休后,都会安分守纪总分从高到低对运动员进行1遍排名。选手的总分为首轮开头前的上马分数加三月在场过的装有竞技的得分和。总分一样的,约定编号较小的运动员排名靠前。

每轮竞赛的势不两立安排与该轮比赛先导前的排名有关:第① 名和第贰 名、第 3
名和第 4名、……、第三K – 1 名和第 2K名、…… 、第一N – 1
名和第3N名,各实行一场交锋。每场比赛胜者得1 分,负者得 0
分。也便是说除了第一批次以外,其余轮竞赛的布局均不能够事先分明,而是要在于选手在事先交锋中的表现。

现给定各个选手的始发分数及其实力值,试总括在Escort 轮比赛过后,排行第 Q
的选手工编织号是多少。大家只要选手的实力值两两分化,且每场比赛中实力值较高的总能获胜。

偶然,想想过去的一年,是极其不好的一年,是极端懊丧的一年,是极端失望的一年,是未曾升级的一年。一贯想写个计算,却直接从未下结论。那两日把温馨2018年写的2011年的工作布署翻了出来,一条一条相比较看了下:

Input

输入的第③行是四个正整数N、安德拉 、Q,每多少个数里面用七个空格隔开分离,表示有
2*N 名运动员、景逸SUV 轮比赛,以及大家关切的排名 Q。

其次行是2N 个非负整数s1, s2, …, s2N,每八个数以内用1个空格隔断,其中si 表示编号为i 的运动员的发端分数。 第③行是2N 个正整数w1 , w2 , …,
w2N,每多个数以内用三个空格隔断,在这之中 wi 表示编号为i 的运动员的实力值。

二零一三年工作陈设与总括:

1.纯熟施用ASP.NET MVC +jQuery+SQL Server
的网站开发架构。很好的形成工作职责。要变成单位此架构下开发的着力人才和着力技术能力。在软件框架结构划设想计、代码编写方面有增加。

计算:这一个马虎粗心,不敢拍胸口讲曾经做到了,不过多少算是应付过去了,只是私有对团结不顺心,觉得这中间照旧有众多索要考订和上学的地点。

2.在场二月份“系统架构划设想计师”考试,争取获得证书,即便拿不到也要总分上直达须要,至少当中两门成绩达到必要。

总计:那么些,只做了一件事,花钱买了架构划设想计的参考资料,其余什么都没干。其实考证不是团结的指标,在存活公司,感觉学习发展上,有些不方便,一是不规范,二是机关小,三是其一都市的软件业也很一般。所以想透过以考促学。未来总的来说,这几个想法值得再仔细商榷。

3.观察一本相比经典的心情学书籍,调理个人的心境和情感。

小结:重要依旧想调适下个人的修改和心情,觉得在那上头有相比较多的贫乏。然则,很遗憾,书是买了却从未看。

4.观望一本职场方面包车型客车书籍,有利于团结的工作和职业规划。

小结:完成学业就在现在以此单位工作四五年了,一向觉得没有进步,无论是专业技术上,还是在品种管理上,如故在此外方面,纵然有时候也能博得领导和共事的承认,不过本人对协调的承认度始终不高,所以想在职场上保有变更。那些是有走动,买了,也读了,而且持续一本,不止贰遍。可是,结果貌似也平素不多大的立异。

5.阅读一本时间管理方面包车型客车书本,更合理设计和选择民用时光,学习时间管理。

总计:那点有点凌乱,李笑来老师的书很好,个人总括下,正是决定大脑,做团结应有做的事。不过,说起不难,做起难,只能稳步来吗。

6.阅读一本英文总结机专业书籍,提升英文阅读能力。

小结:这些纯真没有。

7.周周至少一篇专业技能博客小说。

计算:那些就十二分惭愧了,不用笔者说,大家从本身的博客上也能观看,没有百折不回住。

8.在国家中央期刊杂志上录用或刊载一篇学术杂文。

总括:那一个,仔细想了下,算是吧,而且还费用了不少年华。

9.要有每月总括。

总括:这一个,自从做了那个2011年的规则,压根就从未写过2遍。

Output

出口只有一行,包罗三个平头,即大切诺基 轮竞技甘休后,排名第 Q 的健儿的号子。

如上是对二零一一年规则的计算,真是惨不忍睹啊,没有到位的地方太多了。仔细分析下,或者存在多少个方面包车型地铁因由,一是陈设过高,这一年内不恐怕到位,二是陈设合适,只是人的题材而已。回头想想,除了“系统架构划设想计师”的考证算是相比费心的以外,其它没做好,多数也许因为个人原因。当然,这一年来,也有众多政工是温馨无法控制的(开端找借口了),比如出差到实地支付多少个多月,基本没时间做任何事情。可是完全来说,依然友好个人的来由很多。贰零壹伍年又来了,上班已经2个多星期了,从过大年终步,就在思想这一年的工作安顿,未来是该动手记下来了,虽然某个东西,写下去也不一定本身会一定执行,可是不写出来,不督促协调,很可能更完成持续。

Sample Input

2 4 2
7 6 6 7
10 5 20 15

先说下团结干活儿四五年的感触呢。方今在西面四个公家性质的商讨所上班,重如若做.NET平台下的WinForm和Web开发,面向的客户都以些素质水平较低的用户(此处说的是新闻化素质,不是私有素质教养,相对没有此外贬低用户的情致),项目工作举办算不上顺遂。本身结业后就过来了那么些单位,单位的管理水平和开发水准相比较起来,就连曼彻斯特那样地点的大多数IT集团来讲,都还是有非常大差别。那些年一贯按领导的供给,做那做那,算得上未曾功劳也有苦劳的啊,不过在个人成长规划方面一向不收获,单位也从未别的可供参考的事情成长布署和职业技术培养和陶冶机制。其实,那应当算是小编工作最头疼的地点,干了这么些年没有观察升高,不知晓以后的路怎么走。一起进去的同事,包蕴后来的同事,也有无数跳走的,只是本身家已经安在此刻了,想走也不容许的,即使换个单位,也不见得会比那个好多少,再说,领导对本身也算是比较器重,对自个儿个人在干活和生活上也终于相比扶助,所以,最后依然控制,在那前仆后继干下去。

Sample Output

1

二零一六年,是双重伊始的一年,那段时日,本人也在读书东西,寒假买了些专业方面包车型大巴图书在读,重要的想法依然何等进步自身,那恐怕也是做事几年但又尚未精神进展的情人,都曾面临的难题呢。针对这一年的筹划,也写下去,给协调有个别砥砺吧。

Http

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

二〇一五做事统一筹划:

1.对现有开发平台ASP.NET
MVC有相比深切的明白,包涵对前者设计与编码,都要有感觉获得、看得出来的前进。

2.读书项目管理的有关技能,今年好运获得领导强调,能够起头充当项目管理方面的某些干活了,要抓住那些机遇,让自身具有进步。

3.一心学习SQL
Server相关的知识。说实话自身对那上面很感兴趣,而且事先在那上边到底单位里掌握的相比好的一位了,只是后来任务和取向太多,把它荒废了,近年来年必定要能够在那上边发力。

4.调整工作心理,无论处在什么情形,都要维持一颗积极向上的心态,三个为品种承担、为单位担负、为客户承担的激情,心态倒霉,什么都做糟糕。而且你的行事态度怎样,即便再掩饰,同事也会看在眼里,藏在心中的。

5.改动近期的做事情景,明白好怎么是至关心重视要的事,什么是投机应当主力去做的事。学会时间管理的艺术和精粹的干活章程,跨国集团商讨所这种单位,面对的是部分管理水平不太高的首长,有时候做起工作来,是很厌恶,可是尽力吧,减少被他们不客观的牵着鼻子走的机会。指标是尽量少被打断,学会让她们等一下,学会说不,学会做八个“专业”的软件职员(参考《The
Clean Coder》)。

6.自然每周天篇博客,每月2个总结,那个依然要走的,即便二〇一八年从不坚韧不拔(准确点说是没有做),不过还是有供给在二零一九年继续开展下去的。养成2个脍炙人口的习惯,无论对工作照旧活着,都以那几个有协助的。

7.坚忍不拔读书。小编喜爱读书,也觉得阅读是多少个很好的学习手段,尤其是在以往以此环境下,也是微量可选的读书方法之一。二零一九年近来的读书安排有:

ASP.NET MVC4高级编制程序、
ASP.NET MVC4Web编程(在读)、
ASP.NET MVC4框架揭秘(在读,感觉以偏概全一叶障目,相比为难,大概是因为个人水平原因吗)
编辑可尊敬的JavaScript、
JavaScript语言精彩、
高成效程序员的修养(已读)、
程序员的工作素养(已读)、
飞快开发1000零一夜(在读)、
高速软件开发:原则、形式与实施(C#修订版)、
敏捷技能修炼:敏捷开发与规划的极品实践、
形式:工程化完毕及扩张(设计格局C#版)、
代码整洁之道(The Clean Code英文版,普通话版已经看过,觉得小编写的挺好)、
重构:改良既有代码的布置性(其实在此之前想看那些,可是买了代码整洁之道)、
SQL Server 二零一一尖锐剖析与特性优化(第叁版)、
数据挖掘与数据化运行实战:思路、方法、技艺与行使、
科学普及分布式存款和储蓄系统:原理分析与架构实战、
2个程序员的奋斗史、
程序员,你伤不起、
塞尔维亚Bell格莱德麻将高级打法、

翻阅,要有涉猎的点子,最基本的多个正是要有读书笔记,通过它一是更规范地驾驭当中的道理,二是足以做一些重中之重音信的提炼,现在想看的时候,能够随手拈来,也方便再度学习。要是不做笔记,只是读贰回罢了,往往效果不见得理想。下面列的书目很多,貌似今后都不怎么付之东流了,不过不尝试何地能掌握吧。最想的照旧,能沉下心来,仔细阅读,有所收获呢。

8.俄语学习。印度语印尼语一贯尚未甩掉过,偶尔也会抽时间学习。今年的指标是把ibt的单词背了,相关语法学习下,坚实听大人说的演习,为下一步的想法做准备。

9.杂文发布。因为职称评定审查的难题,不公布是不行的,国家宗旨期刊至少一篇吧。

10.锻练身体。今年过大年病了一场,虽说一点都不大,但像自个儿这么在此在此以前连食欲不振都基本没有的人,也究竟相当大的一场吧。抓实训练,至少每两周要打叁次羽球吧。

Source

分治,归并排序

如上十条,是本人2016年的行事安排,至于今后3至5年的统一筹划,就不贴了。总的来说,算是二个对团结的答应、勉励和监察吗,以期让祥和能抱有升华,也希望我们都能制定贰个安顿,来年再看的时候,肯定会有意料之外的觉醒和收获。

解决思路

刚看那道标题一定想到的是每一轮都全体以分数为第①第2字、编号为第③要害字排序3遍,但那样必然会晚点,所以我们另寻办法。

因为每三次竞技中胜者的分数都只+1,所以只要我们在每一轮过后把胜者和败者分别放入五个数组,大家会发觉,它们各自都以稳步的。

故此为了选取好那特本性,我们利用归并排序,那样就不会爆时间了。

代码

#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;
}