然后枚举第一个和第三个区间即可,中间区间数字的个数也可以通过前缀和来计算
AC代码
#include
#define x first
#define y second...,然后枚举位于两侧的数字的种类。...否则就对左右两侧各拥有多少个数字进行枚举,在中间的区间中找到出现次数最多的数字,设
j j
j
为左右两侧出现的数字个数,
x x
x
为中间区间的最多次数,则代价为
j ∗ 2 + x j*2+x
j...我们可以发现,枚举的中间区间一定是连续的,以
[ 1 , 1 , 1 , 2 , 1 , 2 , 1 , 1 ] [1,1,1,2,1,2,1,1]
[1,1,1,2,1,2,1,1]为例,见下图...我们发现,当两侧数字从小往大递增时,区间长度减少,而递减时,区间长度增加,所以我们可以在枚举两侧数字出现的次数时,记录下状态的改变。因为状态改变时,中间区间的长度是固定的,我们只需要处理左右区间即可。