P4364 [九省联考2018]IIIDX

    • 435通过
    • 1.3K提交
  • 题目提供者 CCF_NOI
  • 评测方式 云端评测
  • 标签 排序 概率论,统计 线段树 贪心 各省省选 2018 高性能
  • 难度 NOI/NOI+/CTSC
  • 时空限制 2000ms / 512MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目背景

    Osu 听过没?那是Konano 最喜欢的一款音乐游戏,而他的梦想就是有一天自己也能做个独特酷炫的音乐游戏。现在,他在世界知名游戏公司KONMAI 内工作,离他的梦想也越来越近了。

    这款音乐游戏内一般都包含了许多歌曲,歌曲越多,玩家越不易玩腻。同时,为了使玩家在游戏上氪更多的金钱花更多的时间,游戏一开始一般都不会将所有曲目公开,有些曲目你需要通关某首特定歌曲才会解锁,而且越晚解锁的曲目难度越高。

    题目描述

    这一天,Konano 接到了一个任务,他需要给正在制作中的游戏《IIIDX》安排曲目 的解锁顺序。游戏内共有n 首曲目,每首曲目都会有一个难度d,游戏内第i 首曲目会在玩家Pass 第$\lfloor \frac{i}{k} \rfloor$ 首曲目后解锁($\lfloor x \rfloor$ 为下取整符号)若$\lfloor \frac{i}{k} \rfloor$ = 0,则说明这首曲目无需解锁

    举个例子:当k = 2 时,第1 首曲目是无需解锁的($\lfloor \frac{1}{2} \rfloor$ = 0),第7 首曲目需要玩家Pass 第$\lfloor \frac{7}{2} \rfloor$ = 3 首曲目才会被解锁。

    Konano 的工作,便是安排这些曲目的顺序,使得每次解锁出的曲子的难度不低于作为条件需要玩家通关的曲子的难度,即使得确定顺序后的曲目的难度对于每个i 满足

    $$d_i \geq d_{\lfloor \frac{i}{k} \rfloor}$$

    当然这难不倒曾经在信息学竞赛摸鱼许久的Konano。那假如是你,你会怎么解决这份任务呢?

    输入输出格式

    输入格式:

    从文件iiidx.in 中读入数据。

    第1 行1 个正整数n 和1 个小数k,n 表示曲目数量,k 其含义如题所示。

    第2 行n 个用空格隔开的正整数d,表示这n 首曲目的难度。

    输出格式:

    输出到文件iiidx.out 中。

    输出1 行n 个整数,按顺序输出安排完曲目顺序后第i 首曲目的难度。

    若有多解,则输出d1 最大的;若仍有多解,则输出d2最大的,以此类推。

    输入输出样例

    输入样例#1: 复制
    4 2.0
    114 514 1919 810
    输出样例#1: 复制
    114 810 514 1919

    说明

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。