P1031 均分紙牌(思維，貪心)

P1031 均分紙牌

題意：

有 n n n堆紙牌，第 i i i堆紙牌有 A i A_i Ai?張，一次操作中，第一堆只可以給第二堆任意張，第 n n n堆只可以給第 n ? 1 n-1 n?1堆任意張，其他堆 i i i，可以給第 i ? 1 i-1 i?1或者 i + 1 i+1 i+1堆任意張，問最少的操作次數使每堆紙牌數量都相同，

思路:

第一堆只能由第二堆給出或得到，使第一堆等于平均值 a v e ave ave，
我們可以假設第一堆不等于 a v e ave ave，那么第二堆要通過一次操作使第一堆等于平均值，
操作之后 A 2 A_2 A2?可能是正值，也可能是負值，在這里負值只是一個概念，可以理解為 A 3 A_3 A3?要給 A 2 a v e ? A 2 A_2~~ave-A_2 A2? ave?A2?張牌，由此遞推下去總能找到使負數變成正數的一堆紙牌，

簡單來說就是，先解決第一堆，使第一堆變成 a v e ave ave然后再，把第二堆當成第一堆重復
決策（如果等于 a v e ave ave就跳過，不然就通過一次操作使它變成 a v e ave ave）

C o d e Code Code

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
int s[110];
int main() {
    int n, sum = 0, ans = 0;
    cin >> n;
    for(int i=1; i<=n; i++) cin >> s[i], sum += s[i];
    sum /= n; //ave
    for(int i=1; i<=n; i++) {
        if(s[i] - sum) s[i+1] += (s[i] - sum), ans++;//決策
    }
    cout << ans;
    return 0;
}