时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld
题目描述
大家好,今天我们来聊聊最大子段和是怎么回事呢?最大子段和相信大家都很熟悉,但是最大子段和又是怎么回事呢?下面就让小编带大家一起了解吧。 最大子段和,其实就是最大子段和了。大家可能会感到很惊讶,最大子段和怎么......
我们将一个数列

的最大子段和的值记为
)
,现在你可以对进行若干次操作,每次操作,你可以选择数列中的一个数字,将其改为

之间的任意一个数。现在,给定整数

,求最少需要操作多少次可以使得
%3Dx)
。
最大子段和是指选出数列中连续且非空的一段使得这段的和最大。
输入描述:
输入第一行是一个整数
,测试用例数。
每个测试用例的第一行包括两个数
,表示数组的长度和需要达到的
。
每个测试用例的第二行输入n个数字
,数组的
个元素。
输入保证对于所有测试用例,有
。
输出描述:
对于每个测试用例,输出一行一个整数,表示令
最少所需的操作次数。
示例1
输入
复制
4
3 0
-1 -1 -1
3 -1
-1 -1 -1
3 -2
-1 -1 -1
7 3
2 -4 3 -1 2 -4 3