Solution P2035

· · 题解

一道简单的模拟。

先来分析样例o(￣▽￣)ブ：

样例长这样：

3 4
10
8
11

第一次操作：最大值为11，输出下标3。

之后平均分配值，发现无法整除(n-1)，于是分给10一个1，平均分配一下，此时，样例变成了：

3 4
16
13
0

很明显，第一个最大，所以第二次输出下标1。

接下来，发现可以直接分配，于是成为了这样：

3 4
0
21
8

第二个最大，输出下标2。之后不能平均分配，然后。。。。。（被作者吃了）

样例就是这亚子，那怎么做呢？？？

  1. 先打擂台找出最大值。

  2. 输出最大值。

  3. 判断能不能整除(n-1)（因为除去这个数还有n-1个数）

    3.1 如果能整除，给除了自己以外的所有数加上a[i]%(n-1)。

    3.2 如果不能，顺序给所有数+1，自己-1。直到能整除，按2.1操作。

好了，就说这么多，现在上C++代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int a[N];
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    while(k--)
    {
        int p,maxa=-1; 
        for(int i=1;i<=n;i++)
            if(a[i]>maxa)
                maxa=a[i],p=i;
        printf("%d\n",p);
        a[p]=0;
        if(maxa%(n-1)==0)
        {
            int t=maxa/(n-1);
            for(int i=1;i<=n;i++) 
                if(i!=p) a[i]+=t;
        }
        else
        {
            for(int i=1;i<=n;i++)
            {
                if(maxa%(n-1)==0) break;
                if(i==p) continue;
                else
                {
                    a[i]++;
                    maxa--;
                }   
            } 
            int t=maxa/(n-1);
            for(int i=1;i<=n;i++)
            {
                if(i!=p) a[i]+=t;
            }
        }
    }
    return 0;
}