06
2019
11

纸牌均分问题的简单实现-贪心

有 N 堆纸牌,编号分别为 1,2,…, N。每堆上有若干张,但纸牌总数必为N 的倍数。可以在任一堆上取若干张纸牌,然后移动。移牌规则为:在编号为 1 堆上取的纸牌,只能移到编号为 2 的堆上;在编号为 N 的堆上取的纸牌,只能移到编号为 N-1 的堆上;其他堆上取的纸牌,可以移到相邻左边或右边的堆上。现在要求找出一种移动方法,用最少的移动次数使每堆上纸牌数都一样多。例如 N=4,4 堆纸牌数分别为:9、8、17、6。设a[i]为第i堆纸牌的张数(0<=i<=n),v为均分后每堆纸牌的张数,s为最小移到次数。用贪心法按照从左到右的顺序移动纸牌。如第i堆(0<i<n)的纸牌数a[i]不等于平均值,则移动一次(即s加1),分两种情况移动:

(1)若a[i]>v,则将a[i]-v张纸牌从第i堆移动到第i+1堆;

(2)若a[i]<v,则将v -a[i]张纸牌从第i+1堆移动到第i堆;

上述两种情况可以统一看作是将a[i]-v张牌从第i堆移动到第i+1堆;移动后有:a[i]=v;a[i+1]=a[i+1]+a[i]-v;在从第i+1堆中取出纸牌补充第i堆的过程中,可能会出现第i+1堆的纸牌数小于零(a[i+1]+a[i]-v<0 )的情况。如n=3,三堆纸牌数为(1,2,27)这时v=10,为了使第一堆数为10,要从第二堆移9张纸牌到第一堆,而第二堆只有2张纸牌可移。从第二堆移出9张到第一堆后,第一堆有10张纸牌,第二堆剩下-7张纸牌,再从第三堆移动17张到第二堆,刚好三堆纸牌数都是10,最后结果是对的,从第二堆移出的牌都可以从第三堆得到。在移动过程中,只是改变了移动的顺序,而移动的次数不变,因此,此题使用贪心法可以求解。

//纸牌问题的贪心实现 
#include <iostream>
using namespace std;
#define max 100
int main()
{
	int n,a[max],v,jishu=0;
	cout << "请输入纸牌的叠数"<<endl; 
	cin >> n;
	cout << "请输入每叠纸牌的数量"<<endl;
	while(jishu++<n)
	{
		cin >> a[jishu];
		v+=a[jishu];
	}
	v/=n;
	jishu=0;
	for(int i=0;i<n;i++){
        if(a[i]!=v){
            a[i+1] -= v - a[i];
            jishu++;
        }
    }
	return 0;
 }

我不得不说,这是最操蛋的解法,不为别的,这种方法会遇到牌数变成-的情况,也就是从别的堆去调,但是,,,这个就是贪心法的经典实例,假装不知道,下期我们再用其他方法来解这个问题!

« 上一篇 下一篇 »

返回顶部
请先 登录 再评论,若不是会员请先 注册