感觉此题难啊,数学还是太渣了,看了半天的题解才算明白了点儿。
题目大意
给一个长度为n且仅由1和-1组成的序列ai, i = 1, 2, ..., n,每个位置都有另一个值vi,要求用某种方案将序列划分为m(0 < m < n)个非空连续子序列,使得所有子序列中和的最大绝对值最小,并且在所有满足上述条件的方案中划分位置的v[i]序列字典序最小。
猜想及证明
记
、
记题目中说的和的最大绝对值的最小值为
有如下几个结论
- 若并且,则
- 若并且,则
- 若,则
证明:
- 第一条结论是显然的
-
对于第二条结论,首先可以肯定,所以。我们要证明对于和为零长度为n的序列,始终存在方案将其划分为i段(i = 1, 2,...,
n),且每一段的和都是-1, 0, 1中一个(即)。这样我们就能得到。证明方法如下:
- 考虑将序列划分为n段,显然这是满足条件的,因为每一段的和都为1或-1
- 现在考虑将这n段中相邻的进行合并,由于整个序列的和为0,故一定能找到一对相邻的段,它们一个的和为-1,另一个为1,令它们合并后,新的段和为0,得到划分为n - 1段的方案
- 继续执行合并。由于整个序列和为0,每一段的和都为-1, 0, 1,所以只要序列中存在1,就一定存在-1,且始终存在相邻或中间仅隔着0的1和-1,且0可以任意合并,所以可以一直合并下去,直到最后仅剩下一个0,即为合并成一段的方案
- 对于第三条结论,如果,我们可以肯定的是。原因是如果每一段的和的绝对值都小于,整个序列的和不可能为。下面我们证明可以构造出的方案。
- 如果,相当于把一堆大小为的物品分成堆,只要保证尽量平均即可
- 如果,由于需要保证每一段非空,我们要换一种方式考虑。考虑先取出个位置,可以做到每一段和的绝对值都为1,也就是说,每一段中可一取出一个数使得剩余部分和为0,这就又变成上面的问题,已经证明对这些部分继续划分,所以
计算方案
这题思维难度很大,就算上面的结论猜到了,敢用了,想不出下面计算字典序最小的方案的算法也是没有用的。
对于并且的情况,由于有且仅有前缀和为0的位置可选,我们仅需要维护一个单调队列,对第i个划分位置入队直到后面的前缀和为0的位置不足时为止,然后取出队中最小的即可。
对于其他情形,我们当前选择的位置受上一个位置限制。假设第个位置为,给定另一个位置,可以作为第个位置当且仅当
这个就有些难。我们对每个S值维护一个单调队列,得到第个位置后,我们访问所有S值在中的单调队列。
看起来是不是很暴力?似乎又要MLE又要TLE的样子?让我们仔细分析空间和时间复杂度,由于我们所有位置都最多入队一次,故空间复杂度为。因为,总共选m次,故总的时间复杂度为。