题解：iCow MP3 Player（P3665）

一、题目分析

本题模拟iCow MP3播放器的选曲逻辑，关键规则如下：

1. 初始评分：每首歌曲i有初始评分$R_i$（1 ≤ $R_i$ ≤ 10,000）
2. 选曲规则：每次播放当前评分最高的歌曲；若有多首评分相同，选择编号最小的
3. 评分分配：播放后，被播放歌曲评分置0，其原有评分$R_i$均分给其他N-1首歌曲
4. 余数处理：若$R_i$无法被N-1整除，多余点数按编号从小到大依次分配

需输出前T首播放的歌曲编号。

二、解题思路

1. 模拟流程：

   • 每次选择当前评分最高且编号最小的歌曲
   • 计算分配给其他歌曲的评分（基础值+余数）
   • 更新所有歌曲评分，重复T次

2. 数据结构：

   • 使用结构体数组存储每首歌曲的评分和编号
   • 重载比较运算符，实现按评分降序、编号升序排序

三、代码解析

#include<cstdio>
#include<algorithm>
using namespace std;

struct Node{
    int x, id;  // x:评分，id:歌曲编号
    bool operator <(const Node&rhs)const{
        return x > rhs.x || (x == rhs.x && id < rhs.id);
    }
}num[20005];

bool cmp(const Node&a, const Node&b){
    return a.id < b.id;  // 按编号升序排序
}

int main(){
    int N, T;
    scanf("%d%d", &N, &T);
    
    // 输入每首歌曲的初始评分
    for(int i = 0; i < N; ++i){
        scanf("%d", &num[i].x);
        num[i].id = i + 1;  // 编号从1开始
    }
    
    // 特判：只有1首歌曲的情况
    if(N == 1){
        for(int i = 0; i < T; ++i) printf("1\n");
        return 0;
    }
    
    // 模拟T次选曲过程
    while(T--){
        // 按评分降序、编号升序排序
        sort(num, num + N);
        
        // 输出当前最高评分的歌曲编号
        printf("%d\n", num[0].id);
        
        int tmp = num[0].id;  // 记录被播放歌曲的编号
        int total = num[0].x; // 被播放歌曲的原评分
        
        // 计算均分的基础值和余数
        int ave = total / (N - 1);
        int yu = total % (N - 1);
        
        // 被播放歌曲评分置0
        num[0].x = 0;
        
        // 给其他歌曲加上基础值
        for(int i = 1; i < N; ++i){
            num[i].x += ave;
        }
        
        // 按编号升序排序，处理余数
        sort(num, num + N, cmp);
        
        int cnt = 0;
        for(int i = 0; ; ++i){
            if(cnt == yu) break;  // 余数分配完即停止
            if(tmp != num[i].id){  // 跳过被播放的歌曲
                ++num[i].x;
                ++cnt;
            }
        }
    }
    return 0;
}

四、关键步骤解析

1. 排序策略：

   • 每次选曲前，按评分降序、编号升序排序，确保优先选择评分最高且编号最小的歌曲
   • 处理余数时，按编号升序排序，确保小编号优先获得额外点数

2. 评分分配：

   • 被播放歌曲原评分$R_i$，均分基础值为$\text{ave} = R_i // (N-1)$，余数为$\text{yu} = R_i \% (N-1)$
   • 其他歌曲先各加基础值$\text{ave}$，再按编号顺序给前$\text{yu}$首歌各加1

3. 特判处理：

   • 当N=1时，直接输出1，避免后续除以0的错误

五、示例解析

以样例输入为例：

3 4
10
8
11

1. 初始状态：
   评分：[10, 8, 11]
   第一次选曲：歌曲3（评分11），播放后评分为[0, 0, 0]
   分配：11点分给歌曲1和2，11 ÷ 2 = 5余1 → 歌曲1得6，歌曲2得5
   新评分：[16, 13, 0]

2. 第二次选曲：
   评分：[16, 13, 0]
   选歌曲1（评分16），播放后评分为[0, 13, 0]
   分配：16点分给歌曲2和3，16 ÷ 2 = 8余0 → 各得8
   新评分：[0, 21, 8]

3. 第三次选曲：
   评分：[0, 21, 8]
   选歌曲2（评分21），播放后评分为[0, 0, 8]
   分配：21点分给歌曲1和3，21 ÷ 2 = 10余1 → 歌曲1得11，歌曲3得10
   新评分：[11, 0, 18]

4. 第四次选曲：
   评分：[11, 0, 18]
   选歌曲3（评分18），输出3

六、复杂度分析

• 时间复杂度：每次选曲需两次排序，每次排序O(N log N)，共T次，总复杂度O(T·N log N)
• 空间复杂度：O(N)，存储歌曲信息

七、注意事项

1. 余数分配顺序：
   必须严格按编号从小到大分配余数，否则可能导致结果错误

2. 特判处理：
   当N=1时，直接输出1，避免后续除以0的错误

3. 排序开销：
   每次选曲两次排序是关键开销，对于更大的N可能需优化（如使用优先队列）

八、优化方向

1. 使用优先队列：
   维护两个优先队列，一个按评分排序，一个按编号排序，每次选曲和更新评分时维护队列状态，可将时间复杂度优化至O(T·log N)

2. 模拟余数分配：
   不排序处理余数，直接按编号顺序遍历，时间复杂度可降至O(T·N)

3. 预处理余数分配：
   预先计算每首歌曲在余数分配中的位置，减少每次遍历开销