一道均分纸牌问题,想知道为什么可以用贪心法这样计算得到最优解?
题目描述有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;
}
求大佬解答一下为什么这样得到的就是最优解?