企业官网建设流程全解析

题目描述

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

• 第iii首曲子有一个初始权值Ri (1≤Ri≤10,000)R_i\ (1 \le R_i \le 10{,}000)Ri​(1≤Ri​≤10,000)。
• 当一首曲子播放完毕，接下来播放的将是所有曲子中权值最大的那首（如果有两首或多首曲子的权值相同，那么这些曲子中编号最小的那首会被选中）。
• 一首曲子在播放结束后，它的权值会被平均地分给其他N−1N-1N−1首曲子，它本身的权值清零。
• 如果一首曲子的权值无法被平均分配（也就是说，无法被N−1N-1N−1整除），那么被N−1N-1N−1除的余数部分将会以111为单位，顺次分配给排名靠前的曲子（也就是说，顺序为曲目111、曲目 $2 \cdots $ 依次下去。当然，刚播放过的那首曲子需要被跳过），直到多出的部分被分配完。

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

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

输入格式

第111行有两个用空格隔开的整数：NNN和TTT。

第222至第N+1N+1N+1行，第i+1i+1i+1行为111个整数RiR_iRi​。

输出格式

输出共TTT行，第iii行输出一个整数，表示 iCow 播放的第iii首曲子。

输入输出样例 #1

输入 #1

3 4 10 8 11

输出 #1

3 1 2 3

说明/提示

每一首曲子播放前，三首曲子的权值分别为：

• [10,8,11][10,8,11][10,8,11]。播放#3\#3#3，11/2=511/2 = 511/2=5，权值余量为111。
• [16,13,0][16,13,0][16,13,0]。播放#1\#1#1，16/2=816/2 = 816/2=8。
• [0,21,8][0,21,8][0,21,8]。播放#2\#2#2，21/2=1021/2 = 1021/2=10，权值余量为111。
• [11,0,18][11,0,18][11,0,18]。播放#3\#3#3，……

【题目解析】

1. 输入与初始化

• 读入n（曲目数量）和t（需要输出的前几首曲目）。
• 用数组r[1..n]存储每首曲子的当前权值。

2. 循环t次，每次找最大权值的曲目

步骤 2.1：选择下一首播放的曲目

intid=1;for(inti=2;i<=n;i++)if(r[i]>r[id])id=i;cout<<id<<"\n";

• 比较所有曲子的权值，选出权值最大的曲目编号（权值相同取编号最小）。
• 输出选中的曲目编号。

3. 更新权值（将当前曲目的权值分给其他曲目）

步骤 3.1：计算平均分配部分和余数

intd=r[id]/(n-1);// 平均分给其他 n-1 首曲子的部分intm=r[id]%(n-1);// 分不完的余数r[id]=0;// 当前曲目权值清零

步骤 3.2：平均分配

for(inti=1;i<=n;i++){if(i==id)continue;r[i]+=d;}

• 其他每首曲子先加上d。

步骤 3.3：余数按曲目编号顺序分配

for(inti=1;i<=n&&m;i++){if(i==id)continue;r[i]++,m--;}

• 从曲目 1 开始，跳过当前播放过的曲目，依次给每首曲子加 1，直到余数分配完。

4. 循环结束

• 重复上述过程t次，输出t行，每行是当前选中的曲目编号。

示例验证（题目样例）

输入：

3 4 10 8 11

初始权值：[10, 8, 11]

1. 最大权值 11 → 曲目 3
   输出3
   分配：d = 11/(3-1)=5，m = 11%2=1
   权值更新：先加5 →[15, 13, 0]，再给曲目1加1 →[16, 13, 0]

2. 最大权值 16 → 曲目 1
   输出1
d = 16/2=8，m = 0
   更新：[0, 21, 8]

3. 最大权值 21 → 曲目 2
   输出2
d = 21/2=10，m = 1
   更新：先加10 →[10, 0, 18]，再给曲目1加1 →[11, 0, 18]

4. 最大权值 18 → 曲目 3
   输出3
   符合样例输出3\n1\n2\n3。

时间复杂度

• 最坏情况：T ≤ 1000，N ≤ 1000
  每次循环O(N)找最大值，O(N)分配权值，总复杂度O(T*N)≈ 1e6，完美运行。

【贴上代码】

#include<iostream>usingnamespacestd;intn,t,r[1010];intmain(){cin>>n>>t;for(inti=1;i<=n;i++)cin>>r[i];while(t--){intid=1;for(inti=2;i<=n;i++)if(r[i]>r[id])id=i;cout<<id<<"\n";intd=r[id]/(n-1);intm=r[id]%(n-1);r[id]=0;for(inti=1;i<=n;i++){if(i==id)continue;r[i]+=d;}for(inti=1;i<=n&&m;i++){if(i==id)continue;r[i]++,m--;}}return0;}