【BZOJ3141】【HNOI2013】旅行

瞎贪心大法好

首先我们可以把\(0\)看成\(-1\),那问题就是把序列分成\(m\)段使得每段和最大值最小。

如果全是\(1\)或者全是\(-1\),那么答案显然为\(\lceil\frac{n}{m}\rceil\)。

对于一般情况,我们可以把相邻的\(1\)和\(-1\)合并再丢到旁边的一个数里面去。那么这两个数就相当于直接删掉了,这样就能转化成上面的情况。合并后的个数为所有数的和。

但是有一个问题就是合并后可能会导致\(n<m\)。

对于这种情况,如果要使答案为\(0\),那么选择的每一段都得是\(0\),也就是后缀和为\(0\)的至少要有\(m\)个。随便维护一下可行最小值即可保证字典序最小。

如果不足\(m\)个,那么答案肯定是\(1\)。不断合并到正好有\(m\)个数显然可行。

求出答案后还要得到最小的字典序。

令\(s\)为后缀和,\(last\)为本段开头,那么每次即寻找一个最小编号位置\(p\)使得\(|s_{last}-s_{p+1}|\le ans\)且\(\frac{|s_{p+1}|}{m}\le ans\)且\(n-p\ge m\)。

前面的部分比较难处理,考虑对于每种\(s\)单独处理。那么每一次合法的\(s\)的范围为\([s_{last}-ans,s_{last}+ans]\),而决策个数为\(m\)次,所以复杂度还是\(O(n)\)的。

代码实现方面,注意不能用deque,会炸空间。。

list是个好东西!用list就不会炸空间啦!

说点什么

您将是第一位评论人!

提醒
wpDiscuz