问题 5491 --数列清零

5491: 数列清零★★★

时间限制: 1 Sec  内存限制: 128 MB
提交: 9  解决: 2
[提交][状态][命题人:]

题目描述

给出一个含有n个整数的数列,你可以将数列中等于0的项替换成任意整数,使得数列中前缀和为0的位置尽量多。

输入

多组数据

第一行一个整数t<=10000,代表数据组数。

对于每组数据:

    第一行一个整数n<=200000,代表数列长度。

    第二行一个长度为n的数列,整数之间用空格隔开。每个整数的绝对值小于等于1e9

输出

每组数据输出一行:一个整数m,前缀和为0的位置最多有m个
样例输入
Copy
4
5
2 0 1 -1 0
3
1000000000 1000000000 0
4
0 0 0 0
9
1 0 0 1 -1 0 1 0 -1
样例输出
Copy
3
1
4
5

提示

对于样例第一组数据,将第二个0变成-2,此时第二、第四、第五个位置前缀和都为0,共3个位置,答案为3.

对于样例第二组数据,将第三个0变成-2000000000,此时第三个位置前缀和为0,共1个位置,答案为1.

来源

[提交][状态]