P2035 iCow

    • 393通过
    • 1.1K提交
  • 题目提供者 LittleZ
  • 评测方式 云端评测
  • 标签 模拟 USACO
  • 难度 普及-
  • 时空限制 1000ms / 128MB

题解

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

    推荐的相关题目 显示

    题目描述

    被无止境的农活压榨得筋疲力尽后,Farmer John打算用他在MP3播放器市场新买的iCow来听些音乐,放松一下。FJ的iCow里存了N(1 <= N <= 1,000)首曲子,按1..N依次编号。至于曲子播放的顺序,则是按一个Farmer John自己设计的算法来决定:

    * 第i首曲子有一个初始权值R_i(1 <= R_i <= 10,000)。

    * 当一首曲子播放完毕,接下来播放的将是所有曲子中权值最大的那首(如果有两首或多首曲子的权值相同,那么这些曲子中编号最小的那首会被选中)。

    * 一首曲子在播放结束后,它的权值会被平均地分给其他N-1首曲子,它本身的权值清零。

    * 如果一首曲子的权值无法被平均分配(也就是说,无法被N-1整除),那么被N-1除的余数部分将会以1为单位,顺次分配给排名靠前的曲子(也就是说,顺序为曲目1、曲目2...依次下去。当然,刚播放过的那首曲子需要被跳过),直到多出的部分被分配完。

    在选定的下一首曲子播放完毕后,这个算法再次被执行,调整曲子的权值,并选出再接下来播放的曲目。

    请你计算一下,按FJ的算法,最先播放的T(1 <= T <= 1000)首曲子分别是哪些。

    输入输出格式

    输入格式:

    第1行: 2个用空格隔开的整数:N 和 T

    第2..N+1行: 第i+1行为1个整数:R_i

    输出格式:

    第1..T行: 第i行为1个整数,表示iCow播放的第i首曲子

    输入输出样例

    输入样例#1: 复制
    3 4
    10
    8
    11
    
    输出样例#1: 复制
    3
    1
    2
    3
    

    说明

    每一首曲子播放前,三首曲子的权值分别为:

    R_1 R_2 R_3

    10 8 11 -> 播放 #3 11/2 = 5, 权值余量 = 1

    16 13 0 -> 播放 #1 16/2 = 8

    0 21 8 -> 播放 #2 21/2 = 10, 权值余量 = 1

    11 0 18 -> 播放 #3 ...

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