P2035 iCow
题目描述
被无止境的农活压榨得筋疲力尽后，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 ...
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 10010
using namespace std;
int n,m,w,s;
int read()
{
,f=; char ch=getchar();
;ch=getchar();}
+ch-',ch=getchar();
return x*f;
}
struct Node
{
int num,w;
}node[N];
int cmp(Node a,Node b)
{
if(a.w==b.w) return a.num<b.num;
return a.w>b.w;
}
int main()
{
n=read(),m=read();
;i<=n;i++)
node[i].w=read(),node[i].num=i;
while(m--)
{
sort(node+,node++n,cmp);
printf(].num);
w=node[].w%(n-),s=node[].w/(n-);
node[].w=;
;i<=n;i++)
) node[i].w+=s+;
else node[i].w+=s;
}
;
}不知道哪错了只得了10分
呜呜，下下来的数据一直过不去
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 10010
using namespace std;
int n,m,p1,p2,a[N],maxn;
int read()
{
,f=; char ch=getchar();
;ch=getchar();}
+ch-',ch=getchar();
return x*f;
}
int main()
{
n=read(),m=read();
;i<=n;i++)
a[i]=read();
)
{
;i<=n;i++)
printf("1\n");
;
}int i;m++;
while(m--)
{
;i<=n;i++)
if(a[i]==maxn)
{
printf("%d\n",i);
break;
}
p1=a[i]/(n-),p2=a[i]%(n-);
a[i]=,maxn=;
;j<=n;j++)
if(i!=j) a[j]+=p1;
;j<=n;j++)
if(!p2) break;
else
if(i!=j) p2--,a[j]++;
;j<=n;j++)
maxn=max(maxn,a[j]);
}
;
}