小红有n堆石头，第i堆包含ai个石头。他想让他的桌子干净，所以他决定把石头都放在第1堆或第n堆。
现在小红可以多次执行以下操作：选择1<=i<j<k<=n,从第j堆中取出两个石头(第j堆至少有两个石头)，然后放在第i堆1个,第k堆1个
现在小红想知道将所有石头移动到第1或第n堆需要的最小次数，或者说这根本不可能。
2417: 石头
时间限制: 2 Sec 内存限制: 128 MB提交: 0 解决: 28
[提交][状态][讨论版][命题人:]
题目描述
输入描述
输入包含多组样例。第一行一个整数T(0<=T<=104)--代表测试样例的组数。
接下来T组数据
每组数据第一行包含一个整数N(3<=N<=105)--代表数组的长度。
接下来是一个整数序列 a1,a2,a3,···,an(1<=ai<=109)--数组元素。
保证n在所有用例中不超过105。
接下来T组数据
每组数据第一行包含一个整数N(3<=N<=105)--代表数组的长度。
接下来是一个整数序列 a1,a2,a3,···,an(1<=ai<=109)--数组元素。
保证n在所有用例中不超过105。
输出描述
每组样例输出一个整数代表答案，如果这是不可能的输出-1。
样例输入
4
5
1 2 2 3 6
3
1 3 1
3
1 2 1
4
3 1 1 2
样例输出
4
-1
1
-1
提示
在第一个测试用例中，最好执行以下操作：
1.选择（i，j，k）=（1，2，5）.数组变为等于[2，0，2，3，7].
2.选择（i，j，k）=（1，3，4）.数组变为等于[3，0，0，4，7].
3.两次选择（i，j，k）=（1，4，5）.数组变为等于[5，0，0，0，9].这个数组满足了要求，因为每块石头都被移动到堆里1和5.
操作总数为4。
来源
-
Anything about this OnlineJudge, Please Contact Administrator. Click add QQ
OJ system based on HUSTOJ Project , UI based on Twitter Bootstrap
Copyright 2016 ACM算法攻关部
关于网站改版