洛谷OJ P1031 均分纸牌

題目 Problem

#

題目連結：https://www.luogu.org/problemnew/show/P1031

敘述 Description

#

有$N$堆纸牌，编号分别为 $1,2,…,N$。每堆上有若干张，但纸牌总数必为$N$的倍数。可以在任一堆上取若干张纸牌，然后移动。

移牌规则为：在编号为$1$堆上取的纸牌，只能移到编号为$2$的堆上；在编号为$N$的堆上取的纸牌，只能移到编号为$N−1$的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。

现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。

例如$N=4$，$4$堆纸牌数分别为：

①$9$②$8$③$17$④$6$

移动$3$次可达到目的：

从 ③ 取$4$张牌放到 ④ $（9,8,13,10）$-> 从 ③ 取333张牌放到 ②$（9,11,10,10）$-> 从 ② 取111张牌放到①$（10,10,10,10）$。

輸入 Input

#

两行

第一行为：$N$（$N$ 堆纸牌，$1 \leq N \leq 100$）

第二行为：$A_1,A_2, … ,A_n$（$N$堆纸牌，每堆纸牌初始数，$1 \leq A_i \leq 10000$）

輸出 Output

#

一行：即所有堆均达到相等时的最少移动次数。

範例輸入 Sample Input

#

4
9 8 17 6

範例輸出 Sample Output

#

3

題解 Solution

#

Re:我没看懂我自己的想法，居然过了 因為沒有中國門號，無法在上面回，就留在這裡了

作法就是把差距移到下一個位置 也就是說這堆的牌把下一堆的牌拿過來平衡 反正下一堆不平衡從下下一堆再拿牌也沒關係

大概就是這樣

程式碼 Accepted Code

#

#include <bits/stdc++.h>
#define _ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
// 參考來源：https://www.luogu.org/discuss/show/75812
int main()
{
    int N,sum=0;
    cin>>N;
    vector<int> enter(N);
    for(int i=0;i<N;i++){
        cin>>enter[i];
        sum+=enter[i];
    }
    int avg=sum/N,timee=0;
    for(int i=0;i<N-1;i++){
        if(enter[i]!=avg){
            enter[i+1]+=enter[i]-avg;
            timee++;
        }
    }
    cout<<timee<<'\n';
    return 0;
}

後記 Afterword

#

稍微看一下討論區，這題思路也蠻多的，可以好好嘗試其他的過程

本人試寫洛谷OJ，把「新手村」都刷光光了 難度排序還不錯，認識一下 NOI 或 NOIP 的題目 之後也會開始寫洛谷OJ的相關題解

（為何不用洛谷裡面的 Blog 呢？）

因為我沒有中國門號 QAQ