#1740. 数圈

    ID: 1740 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 提高 上传者: 标签>CTT赛事:contest1087来源:qoj.ac数据:公开样例枚举

数圈

数圈

题目描述

标题: 数圈 - Problem - QOJ.ac

#5374. 数圈

Statistics

The problem was used in the following contests:

n 个整数排成一圈,定义一次操作为:选择其中一个整数 a,将其变为 −a,并使圈上与其相邻的两个整数加上 a。

求至少操作几次,可以使所有整数均变为非负的。

输入格式

有多组测试数据。

第一行,一个正整数 T(1≤T≤10),表示测试数据组数。

对于每组测试数据,有两行:

  • 第一行,一个正整数 n(3≤n≤105)。
  • 第二行,n 个整数 a1,a2,⋯,an(−104≤ai≤104),这些整数按顺序排成一圈。

输出格式

对于每组测试数据,仅一行一个整数。如果能够使所有整数均变为非负的,输出最小的操作次数;如果不能,则输出 −1。

样例数据

样例输入

3
3
2 2 -3
3
2 2 -5
3
0 0 0

样例输出

5
-1
0

样例解释

初始 2,2,−3⟹−1,−1,3⟹1,−2,2⟹−1,2,0⟹1,1,−1⟹0,0,1 达到目标,操作次数为 5,且显然无法更优。

初始 2,2,−5,显然无法达到目标。

初始 0,0,0,无需操作即已经达到目标。

子任务

  • 任务 1(10 分):n=3,−10≤ai≤10。
  • 任务 2(20 分):n≤50,−10≤ai≤10。
  • 任务 3(30 分):n≤2000。
  • 任务 4(10 分):n≤3×104,∑ai=1
  • 任务 5(10 分):n≤3×104,−10≤∑ai≤10。
  • 任务 6(10 分):n≤3×104。
  • 任务 7(10 分):无特殊条件。

对于 100% 的数据,1≤T≤10,3≤n≤105,−104≤ai≤104。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

3
3
2 2 -3
3
2 2 -5
3
0 0 0
5
-1
0