UC知道均分纸牌（pascal)
来源：百度知道 编辑：UC知道 时间：2024/06/28 05:51:55
问题补充：抱歉,我以为只要是学这个的都应该知道这道题.
具体的题目叙述是这样的:
有 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
输出格式 Output Format
所有堆均达到相等时的最少移动次数。
样例输入
4
9 8 17 6
样例输出
3
这道题怎么做？
要用动态规划（一定！！）
不要用贪心！贪心不行。
分析：
题目要求将每堆纸牌数保证相同，而这个数就是纸牌总数的平均数。换言之，我们只要将每堆纸牌数变成平均数就完成了任务。为了方便处理，我们可以将每堆纸牌数减去平均数后再进行处理。
以题目所给样例数据为例：
N=4，4 堆纸牌数分别为：9 , 8 , 17 , 6，；平均数为10，经过处理后就是：-1 , -2 , 7 , -4，注意一点，这组数据中没有出现“0”的情况。我们从左向右依次移动这些数：
①将1组右移，变成0 , -3 , 7 , -4；
②将2组右移，变成0 , 0 , 4 , -4；
③将3组右移，变成0 , 0 , 0 , 0，完成任务。
这里有一个问题：为什么负数也要移动？其实这是一个逆向思维的过程，将负数组移动等价于将目标组反向移动，比如例子中1 , 2步可以等价于：①将3组左移，变成-1 , 1 , 4 , -4；②将2组左移，变成0 , 0 , 4 , -4。而我们移动负数组可以简化程序结构，应用了等效的思想。（这种数学思想适用于一些需要用模拟解决的问题）如果出现“0”又如何处理呢？如果
左右两端出现0，可以将其略过，中间出现的0，因为需要承担其左右非0组的中转，所以忽略。
总结：
本题属于模拟算法题，较为简单，解题关键在于弄清题目的本质，进而简化模拟过程。
program noip2002_1;
var
a:array[1..100] of integer;
i,j,n,num,ave:integer;
{main}主程序
begin
assign(input,'2002t1.in');
assign(output,'2002t1.out');
reset(input);
rewrite(output);
readln(n);
for i:=1 to n do read(a[i]);
close(input);
for i:=1 to n do a