Michael_Bryant最喜欢的G(al)G(ame)

那些悲伤,那些寂寞,那些几乎让自己放弃生活的希望的痛苦的回忆,绝对绝对不要将它们忘记。

Michael_Bryant最喜欢的番剧

抱歉⋯我已经绝对不可能再获得幸福了,因为⋯我发现⋯ 其实我⋯ 早就已经被幸福包围了

Michael_Bryant正在看的番剧

死亡一点也不温柔,只有无尽的黑暗和孤独。 就算联系得再紧密,人也是孤独的。

bzoj 5249: [2018多省省队联测]IIIDX

题目链接

传送门

Description

【题目背景】

Osu听过没?那是Konano最喜欢的一款音乐游戏,而他的梦想就是有一天自己也能做个独特酷炫的音乐游戏。现在
,他在世界知名游戏公司KONMAI内工作,离他的梦想也越来越近了。这款音乐游戏内一般都包含了许多歌曲,歌曲
越多,玩家越不易玩腻。同时,为了使玩家在游戏上氪更多的金钱花更多的时间,游戏一开始一般都不会将所有曲
目公开,有些曲目你需要通关某首特定歌曲才会解锁,而且越晚解锁的曲目难度越高。

【题目描述】

这一天,Konano接到了一个任务,他需要给正在制作中的游戏《IIIDX》安排曲目的解锁顺序。游戏内共有n首曲目
,每首曲目都会有一个难度d,游戏内第i首曲目会在玩家Pass第trunc(i/k)首曲目后解锁(x为下取整符号)若tru
nc(i/k)=0,则说明这首曲目无需解锁。举个例子:当k=2时,第1首曲目是无需解锁的(trunc(1/2)=0),第7首曲
目需要玩家Pass第trunc(7/2)=3首曲目才会被解锁。Konano的工作,便是安排这些曲目的顺序,使得每次解锁出的
曲子的难度不低于作为条件需要玩家通关的曲子的难度,即使得确定顺序后的曲目的难度对于每个i满足Di≥Dtrun
c(i/k)。当然这难不倒曾经在信息学竞赛摸鱼许久的Konano。那假如是你,你会怎么解决这份任务呢

Input

第1行1个正整数n和1个小数k,n表示曲目数量,k其含义如题所示。
第2行n个用空格隔开的正整数d,表示这n首曲目的难度。
1 ≤ n ≤ 500000
1 < k ≤ 10^9
1 < d ≤ 10^9

Output

输出1行n个整数,按顺序输出安排完曲目顺序后第i首曲目的难度。
若有多解,则输出d1最大的;若仍有多解,则输出d2最大的,以此类推。

Sample Input

4 2.0

114 514 1919 810

Sample Output

114 810 514 1919

想说的话

这个题当时在考场上面由于我一直在想T1的正解(虽然没想出来
所以我这题都没写
然后现在发现其实并不难
虽说当时我写不出来正解
但是
部分分还是能拿点的
就能稍微分高一点。。。

题解

55分做法
线段树加上贪心
但是只要出现了重复的数据贪心的正确性就不保证
所以正解
线段树加上处理之后的贪心
只要把重复的东西单独判定就好了
然后树上查询和
目前bzoj rk2

代码嘛。。
由于做法实在太优
所以大概是你Crtl+c就能轻松rk10-的感觉

代码

Add a Comment

电子邮件地址不会被公开。 必填项已用*标注

隐藏