## 题目背景 [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\，语言方向：C++

```cpp #include <iostream> #include <vector> #include <algorithm> // 计算最小操作次数的函数 int minOperations(std::vector<int>& nums, int n) { int opCount = 0; // 先对序列进行排序，方便后续处理 std::sort(nums.begin(), nums.end()); int i = 0; while (i < n) { int j = i + 1; // 找到相同数字的连续段 while (j < n && nums[j] == nums[i]) { j++; } // 如果连续段长度大于 1，直接删除 if (j - i > 1) { opCount++; i = j; } else { // 否则尝试与后面的数字交换 if (j < n) { std::swap(nums[i], nums[j]); opCount++; } i++; } } return opCount; } int main() { int t; std::cin >> t; while (t--) { int n; std::cin >> n; std::vector<int> nums(n); for (int i = 0; i < n; i++) { std::cin >> nums[i]; } std::cout << minOperations(nums, n) << std::endl; } return 0; } ``` 1. 注意输入数据的范围，尤其是序列长度和数字的取值范围。 2. 对于排序和交换操作，要确保逻辑的正确性，避免出现错误的结果。 3. 在处理多个测试数据时，要注意每次处理完后数据的重置和状态的更新。 [2024-12-21 15:27:41 | AI写代码神器 | 407点数解答]