洛谷 均分纸牌

题号:1031

参考某大神的题解,受了点启发,想了个思路,有可能是和别人是重的,但我还是说一下,毕竟别人的不是特别好懂。

首先读入数据,计算出每个堆上应有的平均分配之后的值。既然最终的目的是要求所有堆都统一为平均值,那我就先不管后面的,先把现在的当前堆管好再说。利用贪心的想法,从左向右遍历,当前堆上的牌数小于平均值就从右面一个堆往过要,大于平均值就把多的全部扔给右面一个堆。过程中有可能出现负数,但是最后肯定是会回到正常的状态。每个堆上的牌至多主动挪出一次,是符合题目要求的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
using namespace std;
int main(){
    int n,arr[101],sum=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
        sum+=arr[i];
    }
    int avg=sum/n;
    int step=0;
    for(int i=1;i<n;i++){
        if(arr[i]<avg){
            step++;
            arr[i+1]-=avg-arr[i];
        }else if(arr[i]>avg){
            step++;
            arr[i+1]+=arr[i]-avg;
        }
    }
    cout<<step;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注