QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 512 MB Total points: 100
统计

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

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

输入格式

有多组测试数据。

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

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

  • 第一行,一个正整数 $n$($3 \leq n \leq 10^5$)。
  • 第二行,$n$ 个整数 $a_1, a_2, \cdots, a_n$($-10^4 \leq a_i \leq 10^4$),这些整数按顺序排成一圈。

输出格式

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

样例数据

样例输入

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

样例输出

5
-1
0

样例解释

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

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

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

子任务

  • 任务 1(10 分):$n = 3$,$-10 \leq a_i \leq 10$。
  • 任务 2(20 分):$n \leq 50$,$-10 \leq a_i \leq 10$。
  • 任务 3(30 分):$n \leq 2\,000$。
  • 任务 4(10 分):$n \leq 3 \times 10^4$,$\sum a_i = 1$
  • 任务 5(10 分):$n \leq 3 \times 10^4$,$-10 \leq \sum a_i \leq 10$。
  • 任务 6(10 分):$n \leq 3 \times 10^4$。
  • 任务 7(10 分):无特殊条件。

对于 $100\%$ 的数据,$1 \leq T \leq 10$,$3 \leq n \leq 10^5$,$-10^4 \leq a_i \leq 10^4$。