问题1189--均分纸牌Ⅱ

1189: 均分纸牌Ⅱ

[命题人 : ]
时间限制 : 2.000 sec  内存限制 : 256 MB

题目描述

在寒假的ACM训练中,Miaoyao做了一道叫“均分纸牌”的题目。题目是这样的: 
有N堆纸牌,编号分别为1,2,…,N。每堆上有若干张,但纸牌总数必为N的倍数。可以在任一堆上取若干张纸牌,然后移动。 
移牌规则为:在编号为1堆上取的纸牌,只能移到编号为2的堆上;在编号为N的堆上取的纸牌,只能移到编号为N-1的堆上;其他堆上取的纸牌,可以移到相邻左边或右边的堆上。 
现在要求找出一种移动方法,用最少的移动次数使每堆上纸牌数都一样多。 
经过努力地思考,Miaoyao终于解出了这道问题。可是,强大的lhl322将这个问题改了一下:首先,这N堆纸牌不再排列成一条线,而是排成环状,也就是说1号堆和N号堆相邻;同时,我们希望移动纸牌的总张数而非次数最小。 
“总张数”是指每次移动的张数之和 也就是说 一张牌移动两次 对总张数的贡献是2而不是1
尽管这只是一个很小的改动,但由于Miaoyao实在是太菜了,这就成功地把他难住了,于是他只好来求助你了。 

输入

第一行一个整数T(1≤T≤5),表示共有T组测试数据
对于每组测试数据,第一行一个整数n(1≤n≤1000000),表示共有n堆纸牌
接下来n行,第i行包括一个整数ai1≤ai≤1000000),表示第i堆纸牌的张数

输出

对于每组测试数据,输出一行,表示最少所需移动的纸牌张数

样例输入 Copy

2
3
100
100
100
4
1
2
5
4

样例输出 Copy

0
4

来源/分类