#P3763. 第2题-多彩的数列
-
1000ms
Tried: 1
Accepted: 1
Difficulty: 4
-
算法标签>双指针
第2题-多彩的数列
解题思路
我们希望通过至多一次删除一个连续子段,使剩余序列所有元素互不相同(“多彩”)。
等价变形:删除子段 [l,r−1] 后,剩下的是前缀 a[0..l−1] 与后缀 a[r..n−1]。要想整体无重复,必须同时满足:
- 前缀内部无重复;
- 后缀内部无重复;
- 前缀元素集合与后缀元素集合不相交。
基于此可以用双指针 + 哈希集合线性求解:
-
先从右往左扩展一个最长无重复后缀。 用集合
Suf自右向左加入元素,遇到第一个重复就停止;此时得到最小的起点r,使得区间[r, n-1]无重复。 -
然后从左往右枚举前缀终点
l,维护前缀集合Pre(始终保证前缀无重复)。- 在每个
l上,当前需要删除的长度是r - l,用它更新答案。 - 若要把
x = a[l]加入前缀,为了保证“前后缀不相交”,就推动r向右,并从Suf中移除经过的元素,直到x不在Suf中为止。 - 若
x已在Pre中,则说明扩展这个前缀会产生内部重复,后续更大的前缀也必然重复,直接停止。
- 在每个
-
在整个过程中,
l与r都只会单调向右移动一次,因此总复杂度为 O(n)。
这个做法本质是两端不相交的去重窗口:右端先准备一个无重复后缀,左端逐步扩展前缀,并用右指针“让路”以消除交集,从而枚举所有合法拆分,最小化删除段长度。
复杂度分析
- 时间复杂度:每个元素最多被左右指针访问/移出一次,O(n);多组数据总计为 O(∑n)(∑n≤2×105)。
- 空间复杂度:两个集合存储当前前缀/后缀的元素,最坏 O(n)。
代码实现
Python
# 读入并输出均在主函数中;核心逻辑封装在函数中
import sys
def min_magic(a):
n = len(a)
# 1) 找到最小的 r 使得 [r..n-1] 为无重复后缀
suf = set()
i = n - 1
while i >= 0 and a[i] not in suf:
suf.add(a[i])
i -= 1
r = i + 1 # 初始无重复后缀的起点
ans = r
# 2) 枚举前缀终点 l,维护前缀集合与右指针 r
pre = set()
for l in range(n):
# 当前删除长度
ans = min(ans, r - l)
x = a[l]
# 若加入会在前缀内造成重复,后续更大前缀也不可能合法,停止
if x in pre:
break
# 让右指针右移,直到后缀中不再包含 x,保持前后缀元素集合不相交
while r < n and x in suf:
suf.remove(a[r])
r += 1
pre.add(x)
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
// 类名必须为 Main,ACM 风格从标准输入读写
import java.io.*;
import java.util.*;
/**
* 思路:双指针 + 两个哈希集合
* 1) 从右向左构造最短起点 r,使 [r..n-1] 无重复;
* 2) 从左向右枚举前缀终点 l,维护前缀集合 pre;
* 对于每个 l,答案候选为 r - l;
* 若要把 a[l] 加入前缀,则右移 r 直到后缀集合不含 a[l];
* 若 a[l] 已在前缀中,则终止。
*/
public class Main {
static int solveOne(int[] a) {
int n = a.length;
// 1) 初始化无重复后缀起点 r
HashSet<Integer> suf = new HashSet<>();
int i = n - 1;
while (i >= 0 && !suf.contains(a[i])) {
suf.add(a[i]);
i--;
}
int r = i + 1;
int ans = r;
// 2) 枚举前缀终点 l
HashSet<Integer> pre = new HashSet<>();
for (int l = 0; l < n; l++) {
ans = Math.min(ans, r - l);
int x = a[l];
// 前缀内部出现重复,无法再扩展,停止
if (pre.contains(x)) break;
// 右移 r 直到后缀不含 x
while (r < n && suf.contains(x)) {
suf.remove(a[r]);
r++;
}
pre.add(x);
}
return ans;
}
// 简单高效输入
static class FastScanner {
private final InputStream in;
private final byte[] buffer = new byte[1 << 16];
private int ptr = 0, len = 0;
FastScanner(InputStream is) { in = is; }
private int read() throws IOException {
if (ptr >= len) {
len = in.read(buffer);
ptr = 0;
if (len <= 0) return -1;
}
return buffer[ptr++];
}
int nextInt() throws IOException {
int c, sgn = 1, x = 0;
do { c = read(); } while (c <= ' ');
if (c == '-') { sgn = -1; c = read(); }
while (c > ' ') {
x = x * 10 + (c - '0');
c = read();
}
return x * sgn;
}
}
public static void main(String[] args) throws Exception {
FastScanner fs = new FastScanner(System.in);
StringBuilder sb = new StringBuilder();
int T = fs.nextInt();
while (T-- > 0) {
int n = fs.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) a[i] = fs.nextInt();
sb.append(solveOne(a)).append('\n');
}
System.out.print(sb.toString());
}
}
C++
// ACM 风格:标准输入输出
#include <bits/stdc++.h>
using namespace std;
/*
思路:双指针 + 集合
1) 自右向左找到最小 r 使 [r..n-1] 无重复;
2) 自左向右枚举 l,维护前缀集合 pre;
- 答案候选为 r - l;
- 将 a[l] 加入前缀前,若和后缀有交集,则右移 r 并从后缀集合移除经过元素;
- 若 a[l] 已在前缀中,无法继续(前缀会重复),停止。
*/
int solve_one(const vector<long long>& a) {
int n = (int)a.size();
// 1) 初始化无重复后缀起点 r
unordered_set<long long> suf;
suf.reserve(n * 2);
int i = n - 1;
while (i >= 0 && !suf.count(a[i])) {
suf.insert(a[i]);
--i;
}
int r = i + 1;
int ans = r;
// 2) 枚举前缀终点 l
unordered_set<long long> pre;
pre.reserve(n * 2);
for (int l = 0; l < n; ++l) {
ans = min(ans, r - l);
long long x = a[l];
// 前缀内出现重复,停止
if (pre.count(x)) break;
// 右移 r,直到后缀不含 x
while (r < n && suf.count(x)) {
suf.erase(a[r]);
++r;
}
pre.insert(x);
}
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 << solve_one(a) << "\n";
}
return 0;
}
题目内容
小明喜欢多彩的数列。在他眼中,一个数列是多彩的,当且仅当数列中的元素互不相同。
具体的,数列 b1,b2,…,bn 。被认为是多彩的,当且仅当对于任意两个不同的下标 ij(1≤i,j≤n,i=j) ,都有 bi=bj 。
这天,小明拿到了一个长为 n 的数列 {a} 。并且,他能选择施展他的魔法,选择一个非负整数 k ,将这个数列中某一个长度为 k 的连续子段删去(剩下的元素按原顺序拼接),这个过程消耗 k 个单位的魔力值。
因为施展魔法后小明会变得很虚弱,所以他只能施展该魔法至多一次。当然,如果 {a} 原来就是多彩的,他也可以不施展。
你能帮助小明计算,让数列 {a} 变得多彩所需的最小魔力值吗?
输入描述
单个测试用例点包含多组数据。
第一行一个正整数 T,表示数据组数。
对于接下来的每一组数据:
第一行一个正整数 n 。
第二行 n 个正整数以空格分隔,表示数列 {a} 。
1≤Σn≤2∗105,1≤ai≤109 。
其中 ∑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 。