#P3665. iCow

    ID: 2666 传统题 1000ms 256MiB 尝试: 2 已通过: 1 难度: 2 上传者: 标签>难度模拟入门普及-USACO 2008 January Bronze

iCow

题目描述

由于厌倦了 farming 的无尽辛劳,Farmer John 决定涉足 MP3 播放器市场,推出新款 iCow。这款播放器存储了 N 首歌曲(1 ≤ N ≤ 1000),编号为 1 到 N,按 Farmer John 设计的算法以“随机”顺序播放:

  1. 初始评分:每首歌曲 i 有一个初始评分 Ri(1 ≤ Ri ≤ 10,000)。
  2. 选曲规则:下一首播放的歌曲总是当前评分最高的。若有多首评分相同,选择编号最小的歌曲。
  3. 评分分配:歌曲播放后,其评分设为 0,原有评分点数均匀分配给其他 N-1 首歌曲。若无法均分(即总点数不能被 N-1 整除),多余的点数按歌曲编号从小到大依次分配(每次加 1,跳过已播放的歌曲)。
  4. 重复过程:每次播放后,基于新的评分重复上述选曲和分配过程。

请确定 iCow 播放的前 T 首歌曲(1 ≤ T ≤ 1000)。

输入格式

  • 第 1 行:两个空格分隔的整数 N 和 T
  • 第 2..N+1 行:第 i+1 行包含一个整数 Ri,表示第 i 首歌曲的初始评分

输出格式

  • 第 1..T 行:每行一个整数,依次为第 1 到第 T 首播放的歌曲编号

输入数据示例 1

3 4  
10  
8  
11  

输出数据示例 1

3  
1  
2  
3  

样例解释

  1. 初始评分:[10, 8, 11]

    • 最高评分是 11(歌曲 3),播放后其评分设为 0。剩余评分总和为 10+8=18,需分配 11 点给其他两首歌。
    • 总分配点数 = 11,N-1=2,11 ÷ 2 = 5 余 1。
    • 歌曲 1 获得 5+1=6 点,歌曲 2 获得 5 点。新评分为:[10+6=16, 8+5=13, 0]。
  2. 第二次选曲:最高评分 16(歌曲 1),播放后设为 0。剩余评分总和为 13+0=13,需分配 16 点给其他两首歌。

    • 16 ÷ 2 = 8 余 0,两首歌各得 8 点。
    • 歌曲 2 新评分:13+8=21,歌曲 3 新评分:0+8=8。评分为:[0, 21, 8]。
  3. 第三次选曲:最高评分 21(歌曲 2),播放后设为 0。剩余评分总和为 0+8=8,需分配 21 点给其他两首歌。

    • 21 ÷ 2 = 10 余 1。
    • 歌曲 1 获得 10+1=11 点,歌曲 3 获得 10 点。新评分为:[0+11=11, 0, 8+10=18]。
  4. 第四次选曲:最高评分 18(歌曲 3),播放后输出 3。

解题思路

  1. 数据结构:使用数组存储每首歌曲的当前评分和编号,每次操作需维护评分的最大值及对应最小编号。
  2. 选曲逻辑
    • 遍历所有歌曲,找到评分最高且编号最小的歌曲作为下一首播放的歌曲。
  3. 评分分配
    • 计算总分配点数(播放歌曲的原评分),剩余歌曲数为 N-1。
    • 基础分配值 = 总点数 // (N-1),余数 = 总点数 % (N-1)。
    • 对未播放的歌曲按编号从小到大遍历,每首先加基础分配值,若有余数则前余数首再加 1。
  4. 重复过程:每次播放后更新评分,直到输出 T 首歌曲。

关键点:每次分配评分时需严格按编号顺序处理余数,确保编号小的歌曲优先获得额外点数。