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 410811

输出样例#1： 

3123

说明

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

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
      
       #include
       
        #include
        
         #include
         
          #define N 10010using namespace std;int n,m,w,s;int read(){    int x=0,f=1; char ch=getchar();    while(ch<'0'||ch>'9'){
    if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9') x=x*10+ch-'0',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.w;}int main(){    n=read(),m=read();    for(int i=1;i<=n;i++)     node[i].w=read(),node[i].num=i;    while(m--)    {        sort(node+1,node+1+n,cmp);        printf("%d\n",node[1].num);        w=node[1].w%(n-1),s=node[1].w/(n-1);        node[1].w=0;        for(int i=2;i<=n;i++)         if(node[i].num<=w+1) node[i].w+=s+1;         else node[i].w+=s;    }    return 0;}
          
         
        
       
      

呜呜，下下来的数据一直过不去

#include
     
      #include
      
       #include
       
        #include
        
         #define N 10010using namespace std;int n,m,p1,p2,a[N],maxn;int read(){    int x=0,f=1; char ch=getchar();    while(ch<'0'||ch>'9'){
   if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();    return  x*f;}int main(){    n=read(),m=read();    for(int i=1;i<=n;i++)     a[i]=read();    if(n==1)    {        for(int i=1;i<=n;i++)         printf("1\n");        return 0;    }int i;m++;    while(m--)    {        for(i=1;i<=n;i++)         if(a[i]==maxn)          {             printf("%d\n",i);             break;         }        p1=a[i]/(n-1),p2=a[i]%(n-1);        a[i]=0,maxn=0;        for(int j=1;j<=n;j++)         if(i!=j) a[j]+=p1;        for(int j=1;j<=n;j++)         if(!p2) break;         else           if(i!=j) p2--,a[j]++;        for(int j=1;j<=n;j++)         maxn=max(maxn,a[j]);    }    return 0;}