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