#P3665. iCow
iCow
题目描述
由于厌倦了 farming 的无尽辛劳,Farmer John 决定涉足 MP3 播放器市场,推出新款 iCow。这款播放器存储了 N 首歌曲(1 ≤ N ≤ 1000),编号为 1 到 N,按 Farmer John 设计的算法以“随机”顺序播放:
- 初始评分:每首歌曲 i 有一个初始评分 Ri(1 ≤ Ri ≤ 10,000)。
- 选曲规则:下一首播放的歌曲总是当前评分最高的。若有多首评分相同,选择编号最小的歌曲。
- 评分分配:歌曲播放后,其评分设为 0,原有评分点数均匀分配给其他 N-1 首歌曲。若无法均分(即总点数不能被 N-1 整除),多余的点数按歌曲编号从小到大依次分配(每次加 1,跳过已播放的歌曲)。
- 重复过程:每次播放后,基于新的评分重复上述选曲和分配过程。
请确定 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
样例解释
-
初始评分:[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]。
-
第二次选曲:最高评分 16(歌曲 1),播放后设为 0。剩余评分总和为 13+0=13,需分配 16 点给其他两首歌。
- 16 ÷ 2 = 8 余 0,两首歌各得 8 点。
- 歌曲 2 新评分:13+8=21,歌曲 3 新评分:0+8=8。评分为:[0, 21, 8]。
-
第三次选曲:最高评分 21(歌曲 2),播放后设为 0。剩余评分总和为 0+8=8,需分配 21 点给其他两首歌。
- 21 ÷ 2 = 10 余 1。
- 歌曲 1 获得 10+1=11 点,歌曲 3 获得 10 点。新评分为:[0+11=11, 0, 8+10=18]。
-
第四次选曲:最高评分 18(歌曲 3),播放后输出 3。
解题思路
- 数据结构:使用数组存储每首歌曲的当前评分和编号,每次操作需维护评分的最大值及对应最小编号。
- 选曲逻辑:
- 遍历所有歌曲,找到评分最高且编号最小的歌曲作为下一首播放的歌曲。
- 评分分配:
- 计算总分配点数(播放歌曲的原评分),剩余歌曲数为 N-1。
- 基础分配值 = 总点数 // (N-1),余数 = 总点数 % (N-1)。
- 对未播放的歌曲按编号从小到大遍历,每首先加基础分配值,若有余数则前余数首再加 1。
- 重复过程:每次播放后更新评分,直到输出 T 首歌曲。
关键点:每次分配评分时需严格按编号顺序处理余数,确保编号小的歌曲优先获得额外点数。