有N堆纸牌,编号分别为1,2,…,N。每堆上有若干张,但纸牌总数必为N的倍数。可以在任一堆上取若干张纸牌,然后移动。
移牌规则为:在编号为1堆上取的纸牌,只能移到编号为2的堆上;在编号为N的堆上取的纸牌,只能移到编号为N−1的堆上;其他堆上取的纸牌,可以移到相邻左边或右边的堆上。
现在要求找出一种移动方法,用最少的移动次数使每堆上纸牌数都一样多。
例如N=4,4堆纸牌数分别为:
①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堆纸牌,每堆纸牌初始数,l≤ Ai ≤10000)
一行:即所有堆均达到相等时的最少移动次数。
输入输出样例 输入样例#1: 4 9 8 17 6
输出样例#1: 3
这是一道经典的贪心算法入门题目,要想用最少的移动次数把所有牌堆都移到相等,正确的贪心策略显然是:每次都移动尽可能多的纸牌。
以正常人的思维来想,肯定是从纸牌数最多的牌堆开始往旁边的牌堆移动纸牌,但是如果要程序中模拟这个过程无疑是比较困难的。因为是计算机处理的缘故,我们可以移动负数张纸牌,且最后达到的效果一样。
一开始先求出牌数的平均值,然后从第1堆开始遍历到第n-1堆牌,如果堆中的牌数不等于平均值,就移动堆中的牌数与平均值的差值张牌(这里无论正负)。接着,下一堆接收到移动过来的牌后,如果牌数不等于平均值,就移动差值张牌…如此循环反复,计算移动次数即可。
1#include <iostream>
2using namespace std;
3const int maxn=10000+5;//数组大小比数据范围稍大
4int a[maxn];
5int main()
6{
7 int n;
8 int ans=0,sum=0,t=0;//ans表示移动次数,t表示要移动的牌数
9 cin>>n;
10 for(int i=0;i<n;i++)//输入数据
11 {
12 cin>>a[i];
13 sum+=a[i];
14 }
15 int avg=sum/n;//求平均值
16 for(int i=0;i<n-1;i++)//遍历每个牌堆(到最后一堆牌数一定等于平均值)
17 {
18 if(a[i]+t!=avg)//如果这个牌堆收到移动过来的牌后牌数不等于平均值,就需要移动
19 {
20 t=a[i]+t-avg;//计算移动的牌数,或正或负。
21 ans++;//移动移动次数加一
22 }
23 else
24 {
25 t=0;//不用移动就是移动0张且次数不变
26 }
27
28 }
29 cout<<ans<<endl;
30 return 0;
31}
以上就是用贪心思想求解均分纸牌问题的整个过程,感谢老铁:淡雅刺影的供稿,你们看懂了吗?
本文分享自 程序员郭震zhenguo 微信公众号,前往查看
如有侵权,请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ,欢迎热爱写作的你一起参与!