QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 512 MB Total points: 100
[+6]

# 5374. 数圈

Statistics

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

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

输入格式

有多组测试数据。

第一行,一个正整数 T1T10),表示测试数据组数。

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

  • 第一行,一个正整数 n3n105)。
  • 第二行,n 个整数 a1,a2,,an104ai104),这些整数按顺序排成一圈。

输出格式

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

样例数据

样例输入

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

样例输出

5
-1
0

样例解释

初始 2,2,31,1,31,2,21,2,01,1,10,0,1 达到目标,操作次数为 5,且显然无法更优。

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

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

子任务

  • 任务 1(10 分):n=310ai10
  • 任务 2(20 分):n5010ai10
  • 任务 3(30 分):n2000
  • 任务 4(10 分):n3×104ai=1
  • 任务 5(10 分):n3×10410ai10
  • 任务 6(10 分):n3×104
  • 任务 7(10 分):无特殊条件。

对于 100% 的数据,1T103n105104ai104