解题思路

我们希望通过至多一次删除一个连续子段，使剩余序列所有元素互不相同（“多彩”）。设删除的是区间 $[l,r]$，则保留下来的部分是前缀 $[1,l-1]$ 与后缀 $[r+1,n]$ 的拼接。因此剩余序列“多彩”的充要条件是：

1. 前缀内部互不相同；
2. 后缀内部互不相同；
3. 前缀与后缀之间也没有重复元素。

于是问题转化为：选择一个前缀长度 $i$（保留 $[1,i]$），和一个后缀起点 $r$（保留 $[r,n]$），满足三条互异性条件，删除长度为 $k=r-i-1$ 的中段，使 $k$ 最小。为了便于实现，令前缀长度用“元素个数”记为 $i$（即保留 $[1..i]$），则删除长度是 $r-i$（当我们用 0-based 写法时，等式会相应平移，思想一致）。

双指针 + 哈希集合 用两个集合维护互异性：

• $S$：维护当前选择的后缀元素集合，使该后缀内部互不相同；
• $P$：维护当前选择的前缀元素集合，使该前缀内部互不相同。

步骤：

1. 先从右向左尽量扩张一个最短的唯一后缀 $[r,n]$：自右向左把元素加入 $S$，一旦遇到重复就停止；此时得到初始 $r$。该 $r$ 是使后缀互异的最小起点。
2. 然后从左到右枚举前缀长度 $i=0,1,2,\dots$。保证加入 $a[i]$ 后 $P$ 仍互异；若出现重复则不能再扩大前缀，循环结束。
3. 对于每个 $i$，为了满足“前缀与后缀互不相同”，当 $a[i]\in S$ 时就右移 $r$，从 $S$ 中移出对应元素，直到冲突消除（此操作不会破坏后缀互异性，因为我们只是在唯一集合中删除左端元素）。
4. 更新答案 $\text{ans}=\min(\text{ans},\; r-i)$。

由于 $r$ 只右移且每个元素至多进入/移出一次，整体线性复杂度。

复杂度分析

• 时间复杂度：$O(n)$（每个元素至多被左右指针各访问/移除一次）。
• 空间复杂度：$O(n)$（哈希集合存放当前前缀/后缀的元素）。

代码实现

Python

import sys

# 计算使序列多彩的最小删除长度（魔力值）
def min_magic(a):
    n = len(a)
    # 先构造最短唯一后缀：r 为后缀起点（0-based）
    S = set()
    r = n
    while r > 0:
        if a[r - 1] in S:
            break
        S.add(a[r - 1])
        r -= 1

    ans = r  # 当前前缀长度为 0 时，删除长度为 r - 0 = r
    P = set()

    # 枚举前缀长度 i（i 表示前缀含有 i 个元素，即索引 0..i-1）
    for i in range(n):
        # 保证前缀互异
        if a[i] in P:
            break
        P.add(a[i])

        # 保证前缀与后缀不相交：若冲突则右移 r
        while r < n and a[i] in S:
            S.remove(a[r])
            r += 1

        # 删除长度 = r - (i + 1)
        ans = min(ans, r - (i + 1))

    return ans

def main():
    data = list(map(int, sys.stdin.read().strip().split()))
    t = data[0]
    idx = 1
    out_lines = []
    for _ in range(t):
        n = data[idx]; idx += 1
        a = data[idx: idx + n]; idx += n
        out_lines.append(str(min_magic(a)))
    print("\n".join(out_lines))

if __name__ == "__main__":
    main()

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    // 计算使序列多彩的最小删除长度
    static int minMagic(int[] a) {
        int n = a.length;
        // 构造最短唯一后缀
        HashSet<Integer> S = new HashSet<>();
        int r = n;
        while (r > 0) {
            int v = a[r - 1];
            if (S.contains(v)) break;
            S.add(v);
            r--;
        }

        int ans = r; // 前缀长度为 0 时的删除长度
        HashSet<Integer> P = new HashSet<>();

        // 枚举前缀长度 i（含 i 个元素）
        for (int i = 0; i < n; i++) {
            int v = a[i];
            // 保证前缀互异
            if (P.contains(v)) break;
            P.add(v);

            // 消除前缀与后缀的交集冲突
            while (r < n && S.contains(v)) {
                S.remove(a[r]);
                r++;
            }

            // 更新答案
            ans = Math.min(ans, r - (i + 1));
        }
        return ans;
    }

    public static void main(String[] args) throws IOException {
        // 根据数据范围，使用 BufferedReader + split 读取
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine().trim());
        StringBuilder sb = new StringBuilder();
        for (int _case = 0; _case < T; _case++) {
            int n = Integer.parseInt(br.readLine().trim());
            String[] parts = br.readLine().trim().split("\\s+");
            int[] a = new int[n];
            for (int i = 0; i < n; i++) a[i] = Integer.parseInt(parts[i]);
            sb.append(minMagic(a)).append('\n');
        }
        System.out.print(sb.toString());
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

// 计算使序列多彩的最小删除长度
int min_magic(const vector<long long>& a) {
    int n = (int)a.size();
    // 构造最短唯一后缀
    unordered_set<long long> S;
    S.reserve(n * 2);
    int r = n;
    while (r > 0) {
        long long v = a[r - 1];
        if (S.count(v)) break;
        S.insert(v);
        --r;
    }

    int ans = r; // 前缀长度为 0 时
    unordered_set<long long> P;
    P.reserve(n * 2);

    // 枚举前缀长度 i（含 i 个元素）
    for (int i = 0; i < n; ++i) {
        long long v = a[i];
        // 保证前缀互异
        if (P.count(v)) break;
        P.insert(v);

        // 消除前缀与后缀的交集冲突
        while (r < n && S.count(v)) {
            S.erase(a[r]);
            ++r;
        }

        // 更新答案
        ans = min(ans, r - (i + 1));
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    if (!(cin >> T)) return 0;
    while (T--) {
        int n; 
        cin >> n;
        vector<long long> a(n);
        for (int i = 0; i < n; ++i) cin >> a[i];
        cout << min_magic(a) << "\n";
    }
    return 0;
}

题目内容

小明喜欢多彩的数列。在他眼中，一个数列是多彩的，当且仅当数列中的元素互不相同.具体的，数列 $b_1,b_2,…,b_n$ 。被认为是多彩的，当且仅当对于任意两个不同的下标 $i,j(1 ≤i,j≤n,i≠j)$， 都有 $b_i≠b_j$ ;

这天，小明拿到了一个长为 $n$ 的数列 {$a$}。并且，他能选择施展他的魔法，选择一个非负整数 $k$ ，将这个数列中某一个长度为k的连续子段删去(剩下的元素按原顺序拼接)，这个过程消耗 $k$ 个单位的魔力值。

因为施展魔法后小明会变得很虚弱，所以他只能施展该魔法至多一次。当然，如果 {$a$} 原来就是多彩的，他也可以不施展。

你能帮助小明计算，让数列 {$a$} 变得多彩所需的最小魔力值吗?

输入描述

单个测试用例点包含多组数据。

第一行一个正整数 $T$，表示数据组数。

对于接下来的每一组数据:

第一行一个正整数 $n$ 。

第二行 $n$ 个正整数以空格分隔，表示数列 {$a$}.

$1≤\sum n≤2*10^5,1≤a_i≤10^9$.

其中 $∑n$ 表示所有 $T$ 组数据的 $n$ 之和。

输出描述

对于每一组数据，输出一行一个整数，表示让 {$a$} 变得多彩所需的最小魔力值。

样例1

输入

3
10
8 7 1 2 7 6 3 4 6 5
5
10 20 30 40 50
7
1 2 1 3 4 5 6

输出

2
0
1

说明

对于第一组样例，删去区间 $[5,6]$ 能使数列变得多彩，消耗 $2$ 点魔力值。可以证明没有更优的方案。

对于第二组样例，原数列已经多彩，故答案为 $0$ 。