| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2895 人关注过本帖
标题:一道均分纸牌问题,想知道为什么可以用贪心法这样计算得到最优解?
只看楼主 加入收藏
青蝶
Rank: 2
等 级:论坛游民
帖 子:160
专家分:51
注 册:2018-2-4
结帖率:92%
收藏
已结贴  问题点数:20 回复次数:5 
一道均分纸牌问题,想知道为什么可以用贪心法这样计算得到最优解?
题目描述
有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

这道题用的贪心法过了,但是不知道为什么这样能保证是最优解。思路是从左到右遍历牌堆,用某堆的牌补齐左边堆的牌,再用右边堆的牌补齐这一堆牌。

代码:
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
using namespace std;

int a[110],N;

int main(void){
    int i,sum=0,average,k=0;
    cin>>N;
    for(i=1;i<=N;i++){
      cin>>a[i];
      sum+=a[i];
}
    average=sum/N;
    for(i=1;i<=N;i++){
        if(a[i]!=average){
            a[i+1]+=a[i]-average;
            k++;
        }
    }
    cout<<k<<endl;
    return 0;
}

求大佬解答一下为什么这样得到的就是最优解?
搜索更多相关主题的帖子: 纸牌 编号 移动 输出 include 
2018-07-18 15:46
kfyniriu
Rank: 6Rank: 6
等 级:侠之大者
威 望:9
帖 子:105
专家分:426
注 册:2018-7-6
收藏
得分:10 
程序最后的出来的结果是 N-1 次移动次数;
如果考虑堆数里面有纸牌数是等于平均数的话,那么(N-1)次还需要减去纸牌数等于平均数的堆数个数;
剩下纸牌数不等于平均数的堆数,还需要考虑2个问题:
1、平均数为5,剩下堆数的纸牌数为:2 3 7 8 最优解是2次
2、平均数为5,剩下堆数的纸牌数为:2 3 6 9 最优解是3次
2018-07-19 10:23
lin5161678
Rank: 12Rank: 12Rank: 12
等 级:贵宾
威 望:45
帖 子:1136
专家分:3729
注 册:2011-12-3
收藏
得分:10 
全平均是 0
不是全平均
N-1-左边连续平均数-右边连续平均数
剩下的 不管什么顺序 反正最快都要全部扫描一次

https://zh.
2018-07-19 15:11
书生牛犊
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:星夜征程
等 级:贵宾
威 望:10
帖 子:1101
专家分:5265
注 册:2015-10-27
收藏
得分:0 
换个表达方式,大家看看能不能便于理解。
测试案例:
 9 3 17 8 10 17 6 10 5 15 16 13 1 10
平均数为10.登记每堆牌缺或多余的牌数如下:
-1 -7 7 -2 0 7 -4 0 -5 5 6 3 -9 0
要想通过最少的移动次数达到平均的目的,就需要把上述集合分割成尽可能多的区间,且每个区间的和均为零。
|-1,-7,7,-2,0,7,-4|0|-5,5|6,3,-9|0|
@kfyniriu提到“最终结果(N-1)次还需要减去纸牌数等于平均数的堆数个数”是不对的。你看我给的这个案例,第五堆本身是等于平均数的,但是由于他的左边卡牌不够多,必须从他这里拿走一些卡牌,然后第五堆再向第六堆拿卡牌才能平衡第五堆。所以这就证明了,不是你本身等于平均数的堆,你就一定不需要移动了,这是错的。用于平衡第一堆的牌只能和第二堆交换,不管第二堆是缺还是余,都得先满足第一堆的需求,第二堆的问题之后再找第三堆解决……

第一个区间有7个堆,所以需要执行6次交换。第二个区间只有一个堆,故不需要交换,第三个区间有两个数,需要1次交换。第4个区间有3个数,需要2次交换,最后一个区间只有一个堆,无需交换。总交换次数=6+0+1+2+0=9


φ(゜▽゜*)♪
2018-07-26 00:09
kfyniriu
Rank: 6Rank: 6
等 级:侠之大者
威 望:9
帖 子:105
专家分:426
注 册:2018-7-6
收藏
得分:0 
回复 4楼 书生牛犊
设平均数是10,每堆的数量为:3 10 10 10 10 10 10 10 10 17  (共10组)
按照楼主算法,从右往左挪,最优解法是9次。
实际上只需要17-7=3+7,一次就足够
2018-07-27 15:01
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:528
帖 子:9025
专家分:54030
注 册:2011-1-18
收藏
得分:0 
回复 5楼 kfyniriu
题目要求只能在相邻的堆之间移动
2018-07-27 15:34
快速回复:一道均分纸牌问题,想知道为什么可以用贪心法这样计算得到最优解?
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.041669 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved