Responsive image

问题 F: 石头

问题 F: 石头

时间限制: 2 Sec  内存限制: 128 MB
提交: 0  解决: 28
[提交][状态][讨论版][命题人:]

题目描述

小红有n堆石头,第i堆包含ai个石头。他想让他的桌子干净,所以他决定把石头都放在第1堆或第n堆。
现在小红可以多次执行以下操作:选择1<=i<j<k<=n,从第j堆中取出两个石头(第j堆至少有两个石头),然后放在第i堆1个,第k堆1个
现在小红想知道将所有石头移动到第1或第n堆需要的最小次数,或者说这根本不可能。

输入描述

输入包含多组样例。第一行一个整数T(0<=T<=104)--代表测试样例的组数。
接下来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。


[提交][状态]
ACM算法攻关部
  • Anything about this OnlineJudge, Please Contact Administrator. Click add QQ

    OJ system based on HUSTOJ Project , UI based on Twitter Bootstrap

    Copyright 2016 ACM算法攻关部
    关于网站改版