题目描述

难度分:$1000$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。

每组数据输入$n(1 \leq n \leq 2 \times 10^5)$和长为$n$的数组$a(1 \leq a[i] \leq n)$。

你可以执行如下操作至多一次：

• 把一个连续子数组都改成同一个数$x$（$x$由你决定），代价为子数组的长度。

要使$a$中所有数都一样，最小代价是多少？

输入样例

8
6
1 2 3 4 5 1
7
1 1 1 1 1 1 1
8
8 8 8 1 2 8 8 8
1
1
2
1 2
3
1 2 3
7
4 3 2 7 1 1 3
9
9 9 2 9 2 5 5 5 3

输出样例

4
0
2
0
1
2
6
7

算法

前后缀分解+二分答案

单调性很容易发现，如果修改一个短的子数组可以让$a$的所有元素相等，那修改一个长的子数组肯定更可以让$a$的所有元素相等，所以考虑二分这个最短的长度。

1. 如果可以找到一个子数组$[l,r]$，前面$[1,l-1]$是一样的数值，后面$[r+1,n]$也是一样的数值（注意前后缀不存在的情况），且$a[l-1]=a[r+1]$，那把$[l,r]$全部修改成$a[l-1]$就可以。
2. 如果找不到这样一个子数组，那么二分给的长度就太小了，应该扩大窗口的长度继续搜索。

接下来的问题就是如何快速判断某一段前缀和后缀是不是由一个数值构成？可以预处理出两个数组$pre$和$suf$。

1. 如果$a[i-1]=a[i]$，那么$pre[i]=pre[i-1]+1$，否则$pre[i]=pre[i-1]$。
2. 同理如果$a[i]=a[i+1]$，那么$suf[i]=suf[i+1]+1$，否则$suf[i]=suf[i+1]$。

这样一来，只要$[1,i]$上是同一个数，就有$pre[i]=i$成立，$[i,n]$上是同一个数，就有$suf[i]=n-i+1$成立。就可以$O(1)$判断前后缀是否是由同一个数值构成了。

复杂度分析

时间复杂度

预处理出$pre$和$suf$的时间复杂度是线性的；$check$函数的时间复杂度是线性的；二分最小代价的值域是$[1,n]$，时间复杂度是$O(log_2n)$的。因此，整个算法的时间复杂度为$O(nlog_2n)$。

空间复杂度

除了输入的$a$数组，主要的空间瓶颈在于$pre$和$suf$两个数组。因此，算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 200010;
int t, n, a[N], pre[N], suf[N];

bool check(int w) {
    for(int r = w; r <= n; r++) {
        int l = r - w + 1;
        if(pre[l - 1] == l - 1 && suf[r + 1] == n - r && (l == 1 || r == n || (a[l - 1] == a[r + 1]))) {
            return true;
        }
    }
    return false;
}

int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        pre[0] = suf[n + 1] = 0;
        pre[1] = 1;
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            if(i >= 2) {
                pre[i] = pre[i - 1] + (a[i] == a[i - 1]? 1: 0);
            }
        }
        if(pre[n] == n) {
            puts("0");
        }else {
            suf[n] = 1;
            for(int i = n - 1; i >= 1; i--) {
                suf[i] = suf[i + 1] + (a[i] == a[i + 1]? 1: 0);
            }
            int l = 1, r = n;
            while(l < r) {
                int mid = l + r >> 1;
                if(check(mid)) {
                    r = mid;
                }else {
                    l = mid + 1;
                }
            }
            printf("%d\n", r);
        }
    }
    return 0;
}