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

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

日子过的真快,恍然之间,自身早已前进二十八周岁的技法了。以前一贯想不领会,为啥小的时候以为日子过的真慢,每1天想长大了,能够做父母做的那多少个事情,比如不要挨打,比如上班赚钱,比如娶个媳妇等等。近来那么些都形成了,却认为日子一天比一天过的快,快到甚至有点恐怖了,那么多的事务并未有做,万一何时看到马克思了,真不佳交待。直到读了李笑来老师的《把日子作为朋友》那本书(尤其推荐各位去读下,肯定会有区别等的得到)才明白,原来是与经历有关。陆虚岁长到6虚岁的一年,占去了人生的伍分之一,而2十虚岁到30虚岁的一年,去只占已走过人生的③%,20:三,这是多大的比例呀,也难怪觉得how
time flies!

Description

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

主旨中介绍的瑞士联邦轮比赛制度,因最早选择于1895年在瑞士联邦进行的国际象棋比赛而得名。它能够当作是淘汰赛与循环赛的迁就,既保证了较量的稳定性,又能使比赛日程不至于过长。
2*N 名编号为 一~二N
的健儿共展开LX570轮比赛。每轮比赛初阶前,以及全数竞技甘休后,都会依据总分从高到低对运动员实行三回排行。选手的总分为第2轮开头前的起来分数加阳春参与过的持有比赛的得分和。总分一样的,约定编号较小的健儿排行靠前。

每轮比赛的周旋安插与该轮比赛起初前的排行有关:第二 名和第三 名、第 3名和第 4名、……、第壹K – 一 名和第 2K名、…… 、第一N – 一名和第1N名,各举行一场比赛。每场比赛胜者得一 分,负者得 0
分。约等于说除了第壹堆次以外,其它轮较量的配备均不可能事先分明,而是要取决于选手在头里交锋中的表现。

现给定各个选手的开端分数及其实力值,试总计在中华V 轮竞技过后,排行第 Q
的选手工编织号是有点。我们假若选手的实力值两两差别,且每场竞赛中实力值较高的总能获胜。

神蹟,想想过去的一年,是极端不佳的一年,是非常黯然的一年,是十分失望的一年,是不曾晋级的一年。一贯想写个小结,却一直尚未下结论。那两日把温馨二〇一八年写的20一三年的办事布置翻了出去,一条一条比较看了下:

Input

输入的首先行是八个正整数N、路虎极光 、Q,每七个数里面用一个空格隔断,表示有
二*N 名选手、RAV肆 轮竞技,以及大家关怀的排行 Q。

第三行是二N 个非负整数s一, s二, …, s二N,每七个数以内用贰个空格隔绝,其中si 表示编号为i 的选手的初步分数。 第三行是2N 个正整数w一 , w2 , …,
w2N,每七个数里面用3个空格隔断,当中 wi 表示编号为i 的运动员的实力值。

2013年干活安排与总括:

1.领会使用ASP.NET MVC +jQuery+SQL Server
的网址开发框架结构。很好的完成工作任务。要成为单位此架构下开发的主旨人才和主旨技术能力。在软件架构设计、代码编写方面有增加。

小结:那个马虎大意,不敢拍胸口讲曾经做到了,不过多少算是应付过去了,只是个体对团结不比意,觉得那中间依然有为数不少亟需修正和上学的地点。

贰.列席1月份“系统架构划设想计师”考试,争取得到证书,尽管拿不到也要总分上达标供给,至少当中两门成绩达到须要。

计算:这一个,只做了一件事,花钱买了架构划设想计的参考资料,别的什么都没干。其实考证不是自个儿的指标,在现有公司,感觉学习发展上,有个别不便,壹是不专业,二是部门小,三是其1都市的软件业也很一般。所以想透过以考促学。以往总的来说,这么些想法值得再细致商榷。

三.观察1本比较经典的心境学书籍,调理个人的情怀和心绪。

总结:主要仍然想调适下个人的改动和心绪,觉得在那上头有相比较多的不足。不过,很遗憾,书是买了却并未有看。

四.观看1本职场方面包车型地铁图书,有利于团结的工作和职业规划。

小结:毕业就在到现在以此单位工作四伍年了,平昔觉得未有进步,无论是专业技术上,依然在品种管理上,照旧在其余地点,就算有时候也能收获领导和共事的认同,但是自身对协调的承认度始终不高,所以想在职场上全体变动。那个是有走动,买了,也读了,而且持续1本,不止一回。然而,结果貌似也从不多大的改进。

伍.阅读一本时间管理方面包车型地铁书本,更客观设计和选拔民用时间,学习时间管理。

计算:那点有点凌乱,李笑来老师的书很好,个人总括下,正是决定大脑,做要好应有做的事。可是,谈到不难,做起难,只好稳步来呢。

六.阅读1本英文总结机专业书籍,进步英文阅读能力。

小结:那么些纯真未有。

七.周周至少一篇专业技能博客文章。

计算:这一个就那一个惭愧了,不用自身说,大家从本人的博客上也能收看,未有持之以恒住。

八.在江山焦点期刊杂志上录用或宣布一篇学术散文。

小结:那一个,仔细想了下,算是吧,而且还开销了很多时光。

玖.要有每月计算。

小结:那些,自从做了那几个201三年的条条框框,压根就向来不写过1次。

Output

输出唯有1行,包含多少个平头,即RAV4 轮竞赛截至后,排名第 Q 的选手的数码。

上述是对20一3年规则的下结论,真是惨不忍睹啊,未有完结的地点太多了。仔细分析下,恐怕存在七个方面的由来,1是安排过高,这年内无法形成,二是安插合适,只是人的题目而已。回头想想,除了“系统架构划设想计师”的考究算是相比较勤奋的以外,别的没做好,多数或许因为个人原因。当然,今年来,也有成都百货上千工作是友善不可能控制的(伊始找借口了),比如出差到现场支付多个多月,基本没时间做其余业务。可是全部来说,照旧本人个人的原委很多。201四年又来了,上班已经2个多星期了,从过年开头,就在思虑这年的劳作规划,未来是该入手记下来了,即便某些东西,写下去也未必自身会肯定执行,可是不写出来,不督促协调,很或者更达成持续。

Sample Input

2 4 2
7 6 6 7
10 5 20 15

先说下自个儿干活儿4五年的感受啊。近来在西面三个公家性质的研究所上班,首若是做.NET平台下的WinForm和Web开发,面向的客户都是些素质水平较低的用户(此处说的是音信化素质,不是个体素质教养,相对未有任何贬低用户的意思),项目工作进展算不上顺遂。自个儿毕业后就到来了这几个单位,单位的管理水平和开销水平相比较起来,就连萨拉热窝如此地点的大多数IT集团来讲,都照旧有相当大差异。那么些年一向按领导的供给,做那做那,算得上未曾功劳也有苦劳的啊,不过在个人成长规划方面并未有收获,单位也未曾任何可供参考的饭碗成长安插和职业培训机制。其实,那应当算是本身工作最头痛的地点,干了那几个年未有看到升高,不明了现在的路怎么走。1起跻身的同事,包含后来的同事,也有不少跳走的,只是本身家已经安在那时了,想走也不只怕的,即便换个单位,也不见得会比这几个好多少,再说,领导对本身也好不不难对比讲究,对本人个人在做事和生存上也终归比较协助,所以,最终依旧控制,在那心想事成干下去。

Sample Output

1

201四年,是重复起首的一年,那段时日,自身也在上学东西,寒假买了些专业方面包车型大巴书本在读,首要的想法依然怎样升级本身,那恐怕也是干活几年但又未有实质进展的意中人,都曾面临的难点呢。针对这个时候的宏图,也写下来,给协调有个别砥砺吧。

Http

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

2014做事规划:

1.对现有开发平台ASP.NET
MVC有比较尖锐的问询,包罗对前者设计与编码,都要有感觉获得、看得出来的进步。

二.上学项目管理的连带技能,今年好运获得领导强调,能够开首充当项目管理方面的有的做事了,要引发那么些时机,让祥和有所升级。

三.潜心读书SQL
Server相关的学问。说实话本身对那上头很感兴趣,而且从前在这地方终于单位里明白的可比好的1个人了,只是后来职务和倾向太多,把它荒废了,而二〇一玖年必定要能够在那上边发力。

四.调动工作心绪,无论处在怎样意况,都要维持一颗积极向上的情怀,三个为项目负责、为单位担负、为客户承担的心思,心态不好,什么都做不佳。而且你的做事态势怎样,即便再掩饰,同事也会看在眼里,藏在心中的。

伍.改变如今的干活场景,通晓好怎么是首要的事,什么是协调应当老将去做的事。学会时间管理的方法和非凡的劳作格局,国有公司切磋所那种单位,面对的是部分管理水平不太高的集团主,有时候做起工作来,是很看不惯,不过尽力吧,收缩被她们不客观的牵着鼻子走的机会。指标是尽量少被打断,学会让他们等一下,学会说不,学会做2个“专业”的软件职员(参考《The
Clean Coder》)。

陆.本来每一周一篇博客,每月一个总计,那一个依然要走的,即使2018年向来不坚持不渝(准确点说是未有做),可是照旧有必不可缺在今年继续进行下去的。养成3个卓越的习惯,无论对工作仍旧活着,都以老大有救助的。

柒.滴水穿石读书。笔者爱好阅读,也以为阅读是贰个很好的上学手段,特别是在未来这些环境下,也是为数不多可选的学习方法之1。二〇一玖年一时半刻的翻阅安排有:

ASP.NET MVC4高级编制程序、
ASP.NET MVC4Web编程(在读)、
ASP.NET MVC4框架揭秘(在读,感觉以偏概全以偏概全,比较吃力,大概是因为个人水平原因吗)
编辑可爱慕的JavaScript、
JavaScript语言精彩、
高作用程序员的修养(已读)、
程序员的职业素养(已读)、
快快开发1000零一夜(在读)、
急迅软件开发:原则、格局与实践(C#修订版)、
相当的慢技能修炼:敏捷开发与陈设的特等实践、
形式:工程化落成及扩张(设计格局C#版)、
代码整洁之道(The Clean Code英文版,汉语版已经看过,觉得小编写的挺好)、
重构:改良既有代码的宏图(其实后边想看那一个,不过买了代码整洁之道)、
SQL Server 2011中肯解析与天性优化(第二版)、
多少挖掘与数据化运转实战:思路、方法、技艺与运用、
广泛分布式存款和储蓄系统:原理分析与架构实战、
2个程序员的奋斗史、
程序员,你伤不起、
圣Juan麻将高级打法、

读书,要有阅读的艺术,最基本的贰个便是要有读书笔记,通过它一是越来越纯粹地明白在那之中的道理,2是足以做一些根本音讯的提炼,以后想看的时候,能够随手拈来,也有益再一次学习。即使不做速记,只是读三次罢了,往往效果不见得理想。上边列的书目很多,貌似今后都有个别一曝十寒了,不过不尝试哪儿能了然呢。最想的依然,能沉下心来,仔细翻阅,有所收获吧。

8.意大利语学习。葡萄牙语平昔未曾舍弃过,偶尔也会抽时间学习。二〇一九年的对象是把ibt的单词背了,相关语艺术学习下,坚实听他们讲的磨练,为下一步的想法做准备。

九.杂谈公布。因为职称评定审查的题材,不登出是老大的,国家中央期刊至少一篇吧。

10.练习肢体。二〇一玖年度岁病了一场,虽说十分小,但像本身如此在此以前连皮肤瘙痒都基本没有的人,也好不简单相当大的一场吧。抓好练习,至少每两周要打二遍羽球吧。

Source

分治,归并排序

上述10条,是自家201肆年的办事布署,至于未来三至五年的宏图,就不贴了。总的来说,算是三个对协调的允诺、勉励和监督吗,以期让祥和能具备升华,也希望我们都能制定1个布置,来年再看的时候,肯定会有意外的醒悟和取得。

消除思路

刚看那道标题一定想到的是每壹轮都全部以分数为率先至关心重视要字、编号为第一重中之重字排序1回,但如此必然会晚点,所以大家另寻办法。

因为每3次交锋后胜者的分数都只+一,所以借使我们在每壹轮过后把胜者和败者分别放入三个数组,大家会发觉,它们分别都以上行下效的。

故此为了选用好那么些特性,大家利用归并排序,那样就不会爆时间了。

代码

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