題目描述

有N堆紙牌，編號分別為1,2,…,N。每堆上有若干張，但紙牌總數(shù)必為N的倍數(shù)。可以在任一堆上取若干張紙牌，然后移動。

移牌規(guī)則為：在編號為1堆上取的紙牌，只能移到編號為2的堆上；在編號為N的堆上取的紙牌，只能移到編號為N?1的堆上；其他堆上取的紙牌，可以移到相鄰左邊或右邊的堆上。

現(xiàn)在要求找出一種移動方法，用最少的移動次數(shù)使每堆上紙牌數(shù)都一樣多。

例如N=4，4堆紙牌數(shù)分別為：

①9②8③17④6

移動3次可達到目的：

從 ③ 取4張牌放到 ④ （9,8,13,10）-> 從 ③取3張牌放到 ②（9,11,10,10）-> 從②取1張牌放到①（10,10,10,10）。

輸入輸出格式

輸入格式：

兩行

第一行為：N（N堆紙牌，1≤N≤100）

第二行為：A1,A2,…,An（N堆紙牌，每堆紙牌初始數(shù)，l≤ Ai ≤10000）

輸出格式：

一行：即所有堆均達到相等時的最少移動次數(shù)。

輸入輸出樣例

輸入樣例#1：

4
9 8 17 6

輸出樣例#1：

3

分析

• 這是一道經(jīng)典的貪心算法入門題目，要想用最少的移動次數(shù)把所有牌堆都移到相等，正確的貪心策略顯然是：每次都移動盡可能多的紙牌。
• 以正常人的思維來想，肯定是從紙牌數(shù)最多的牌堆開始往旁邊的牌堆移動紙牌，但是如果要程序中模擬這個過程無疑是比較困難的。因為是計算機處理的緣故，我們可以移動負數(shù)張紙牌，且最后達到的效果一樣。
• 一開始先求出牌數(shù)的平均值，然后從第1堆開始遍歷到第n-1堆牌，如果堆中的牌數(shù)不等于平均值，就移動堆中的牌數(shù)與平均值的差值張牌（這里無論正負）。接著，下一堆接收到移動過來的牌后，如果牌數(shù)不等于平均值，就移動差值張牌…如此循環(huán)反復(fù)，計算移動次數(shù)即可。

代碼如下

#include <iostream> using namespace std; const int maxn=10000+5;//數(shù)組大小比數(shù)據(jù)范圍稍大 int a[maxn]; int main() {int n;int ans=0,sum=0,t=0;//ans表示移動次數(shù)，t表示要移動的牌數(shù)cin>>n;for(int i=0;i<n;i++)//輸入數(shù)據(jù){cin>>a[i];sum+=a[i];}int avg=sum/n;//求平均值for(int i=0;i<n-1;i++)//遍歷每個牌堆（到最后一堆牌數(shù)一定等于平均值）{if(a[i]+t!=avg)//如果這個牌堆收到移動過來的牌后牌數(shù)不等于平均值，就需要移動{t=a[i]+t-avg;//計算移動的牌數(shù)，或正或負。ans++;//移動移動次數(shù)加一}else{t=0;//不用移動就是移動0張且次數(shù)不變}}cout<<ans<<endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的P1031 均分纸牌（经典贪心）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。