思路与神奇操作
这道题我们首先会不可避免地对每一个序列进行排序。每一个序列的顶部的和就是最大和,而次大和就是 \(n-1\)个序列的最大和 和 一个头部值最小的序列的头部值 之和。所以,我们把视野缩小一些,讨论两个序列的合并。
这道题我们首先会不可避免地对每一个序列进行排序。每一个序列的顶部的和就是最大和,而次大和就是 \(n-1\)个序列的最大和 和 一个头部值最小的序列的头部值 之和。所以,我们把视野缩小一些,讨论两个序列的合并。
单调队列的主要目标其实跟单调栈的主要目标比较相似,都是在一个单调问题中,直接排除一些可以排除的答案进行运算。
在本题中,我们会采用单调队列来解决。首先,我们采用前缀和来进行快速计算。然后,在前缀的前提下,我们会在本题中使用一个策略,那就是:如果有两个位置的前缀和\(sum[i]>sum[j],其中i<j\),那么处于\(i\)位置的元素对于我们来讲,是毫无用处的。原因是,如果我们要在\(m\)长度内获得和最大的子序列,对于一个这样前缀和又大、又靠前的元素,最优解绝不是由这个元素组成的。
我们来用几个代码块来简述我们的策略。