「alfr round 3」b：巧用贪心与栈，求解序列swap & delete最小操作数

为了解决这个问题，我们可以考虑使用贪心算法和栈数据结构来模拟操作过程，以达到最小操作次数。 下面是解决问题的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. 剩余元素的删除：在遍历完所有元素后，栈中可能还剩余一些元素。这些元素不能通过删除相同元素的操作去除，因此每个剩余元素都需要通过一次删除一个元素的操作去除。这部分操作次数需要额外计算。 ######[AI写代码神器 | 637点数解答 | 2024-12-21 14:56:50]