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



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

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