洛谷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

1
2
4
9 8 17 6

範例輸出 Sample Output

1
3

題解 Solution

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

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

大概就是這樣

程式碼 Accepted Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#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


洛谷OJ P1031 均分纸牌
https://blog.yangjerry.tw/2019/01/19/lg-1031/
作者
Jerry Yang
發布於
2019年1月19日
許可協議