# 「alfr round 3」b swap & delete ## 题目背景 [english statement](https://www.luogu.com.cn/problem/u517304). you must submit your code at the chinese version of the statement. ## 题目描述 给定一个长为 $n$ 的序列 $a_1, a_2,a_3, \dots ,a_n$，你需要执行 $k$ 次操作使这个序列为空。 每次操作可以执行下列内容之一： 1. 选择两个数 $i, j$，交换 $a_i, a_j$（需要满足 $1 \le i < j \le n$）。 2. 选择两个数 $i, j$，删除 $a_i,a_{i+1}, \dots ,a_j$（需要满足 $1 \le i \le j \le n$，且 $a_i = a_j$）。 请输出最小的操作数 $k$。 ## 输入格式 第一行输入一个正整数 $t$（$1 \le t \le 5$），表示有 $t$ 个测试数据。 对于每个测试数据： 第一行输入一个正整数 $n$（$1 \le n \le 10^5$），表示序列长度为 $n$。 第二行输入 $n$ 个正整数 $a_1,a_2 \dots a_n$（$0 \le a_i \le 10^9$）。 ## 输出格式 对于每个测试数据输出一个正整数 $k$，表示最少的操作次数。 ## 样例 #1 ### 样例输入 #1 ``` 2 5 1 2 3 2 3 3 1000000000 1000000000 99999999 ``` ### 样例输出 #1 ``` 2 2 ``` ## 提示 ### 数据范围 | 子任务 | 分值 | 限制 | | :----------: | :----------: | :----------: | | $1$ | $10$ | $n\le 3$ | | $2$ | $20$ | $n\le 10$ | | $3$ | $20$ | $a_i\le 2$ | | $4$ | $10$ | 保证所有 $a_i$ 相等 | | $5$ | $40$ | - | 对于 $100\%$ 的数据，$1\le t \le 5$，$1\le n\

为了解决这个问题，我们可以考虑使用贪心算法和栈数据结构来模拟操作过程，以达到最小操作次数。 下面是解决问题的Python代码： ```python def min_operations(t, test_cases): results = [] for case in test_cases: n = case[0] a = case[1] stack = [] # 用于模拟操作的栈 visited = set() # 记录已经访问过的元素（即已经在栈中） operations = 0 # 记录操作次数 for num in a: if num in visited: # 如果当前数字已经在栈中，则找到栈中对应的索引并进行删除操作 start_idx = None for i, val in enumerate(stack): if val == num: start_idx = i break # 删除从start_idx到当前栈顶的所有元素（模拟删除操作） stack = stack[:start_idx] operations += 1 else: # 否则，将数字压入栈中（模拟交换操作，但实际上是直接放入） stack.append(num) visited.add(num) # 栈中剩余的每个元素都需要单独删除（模拟删除一个元素的操作） # 因为题目要求最终序列为空，而栈中剩余的元素不能通过删除相同元素的操作去除 # 所以每个剩余元素都需要通过一次删除一个元素的操作去除 while stack: stack.pop() operations += 1 results.append(operations) return results # 读取输入 import sys input = sys.stdin.read data = input().split() t = int(data[0]) index = 1 test_cases = [] for _ in range(t): n = int(data[index]) index += 1 a = list(map(int, data[index:index+n])) index += n test_cases.append((n, a)) # 输出结果 results = min_operations(t, test_cases) for res in results: print(res) ``` 额外需要注意的逻辑点： 1. 栈的使用：我们使用栈来模拟序列的变化过程，因为栈的LIFO（后进先出）特性非常适合模拟删除连续相同元素的操作。 2. visited集合：使用集合来记录已经访问过的元素（即在栈中的元素），以便快速判断当前元素是否已经在栈中，从而决定执行删除操作还是压栈操作。 3. 剩余元素的删除：在遍历完所有元素后，栈中可能还剩余一些元素。这些元素不能通过删除相同元素的操作去除，因此每个剩余元素都需要通过一次删除一个元素的操作去除。这部分操作次数需要额外计算。 [2024-12-21 14:56:50 | AI写代码神器 | 637点数解答]