题目描述 给定一个长为 nn 的序列 a_1, a_2,a_3, \dots ,a_na 1 ,a 2 ,a 3 ,…,a n ，你需要执行 kk 次操作使这个序列为空。 每次操作可以执行下列内容之一： 选择两个数 i, ji,j，交换 a_i, a_ja i ,a j （需要满足 1 \le i < j \le n1≤i<j≤n）。 选择两个数 i, ji,j，删除 a_i,a_{i+1}, \dots ,a_ja i ,a i+1 ,…,a j （需要满足 1 \le i \le j \le n1≤i≤j≤n，且 a_i = a_ja i =a j ）。 请输出最小的操作数 kk。 输入格式 第一行输入一个正整数 tt（1 \le t \le 51≤t≤5），表示有 tt 个测试数据。 对于每个测试数据： 第一行输入一个正整数 nn（1 \le n \le 10^51≤n≤10 5 ），表示序列长度为 nn。 第二行输入 nn 个正整数 a_1,a_2 \dots a_na 1 ,a 2 …a n （0 \le a_i \le 10^90≤a i ≤10 9 ）。 输出格式 对于每个测试数据输出一个正整数 kk，表示最少的操作次数。 输入输出样例 输入 #1 复制 2 5 1 2 3 2 3 3 1000000000 1000000000 99999999 输出 #1 复制 2 2 说明/提示 数据范围 子任务 分值 限制 11 1010 n\le 3n≤3 22 2020 n\le 10n≤10 33 2020 a_i\le 2a i ≤2 44 1010 保证所有 a_ia i 相等 55 4040 - 对于 100\%100% 的数据，1\le t \le 51≤t≤5，1\le n\le 10^51≤n≤10 5 ，0\le a_i\le 10^90≤a i ≤10 9 。，语言方向：C++，系统环境：Windows
```cpp #include <iostream> #include <vector> #include <unordered_map> using namespace std; int minOperationsToEmptyArray(int n, const vector<int>& a) { unordered_map<int, int> countMap; for (int num : a) { countMap[num]++; } // 记录最大连续相同元素长度 int maxConsecutive = 0; int currentConsecutive = 1; for (int i = 1; i < n; ++i) { if (a[i] == a[i - 1]) { currentConsecutive++; } else { maxConsecutive = max(maxConsecutive, currentConsecutive); currentConsecutive = 1; } } maxConsecutive = max(maxConsecutive, currentConsecutive); // 如果存在超过2个的连续相同元素，直接返回这些元素的数量除以2向上取整 if (maxConsecutive > 2) { return (n + 1) / 2; } // 如果所有元素都不同或者最多有两个连续相同的元素 int uniqueElements = countMap.size(); if (uniqueElements == n) { return n - 1; } else { return uniqueElements; } } int main() { int t; cin >> t; while (t--) { int n; cin >> n; vector<int> a(n); for (int& num : a) { cin >> num; } cout << minOperationsToEmptyArray(n, a) << endl; } return 0; } ``` 代码 - 使用 `unordered_map` 统计每个元素出现次数。 - 遍历数组，记录最大连续相同元素长度。 - 根据最大连续相同元素长度判断操作次数。 - 对于测试用例，循环读入数据并输出结果。 额外需要注意的地方： 1. 输入数据量较大时，使用快速读写方法优化性能。 2. 处理边界情况，如数组长度为1或所有元素相同。 3. 考虑到内存限制，避免不必要的空间开销。 [2024-12-21 17:35:25 | AI写代码神器 | 462点数解答]
相关提问
- 题目描述 给定一个长为 nn 的序列 a_1, a_2,a_3, \dots ,a_na 1 ,a 2 ,a 3 ,…,a n ，你需要执行 kk 次操作使这个序列为空。 每次操作可以执行下列内容之一： 选择两个数 i, ji,j，交换 a_i, a_ja i ,a j （需要满足 1 \le i < j \le n1≤i<j≤n）。 选择两个数 i, ji,j，删除 a_i,a_{i+1}, \dots ,a_ja i ,a i+1 ,…,a j （需要满足 1 \le i \le j \le n1≤i≤j≤n，且 a_i = a_ja i =a j ）。 请输出最小的操作数 kk。 输入格式 第一行输入一个正整数 tt（1 \le t \le 51≤t≤5），表示有 tt 个测试数据。 对于每个测试数据： 第一行输入一个正整数 nn（1 \le n \le 10^51≤n≤10 5 ），表示序列长度为 nn。 第二行输入 nn 个正整数 a_1,a_2 \dots a_na 1 ,a 2 …a n （0 \le a_i \le 10^90≤a i ≤10 9 ）。 输出格式 对于每个测试数据输出一个正整数 kk，表示最少的操作次数。 输入输出样例 输入 #1 复制 2 5 1 2 3 2 3 3 1000000000 1000000000 99999999 输出 #1 复制 2 2 说明/提示 数据范围 子任务 分值 限制 11 1010 n\le 3n≤3 22 2020 n\le 10n≤10 33 2020 a_i\le 2a i ≤2 44 1010 保证所有 a_ia i 相等 55 4040 - 对于 100\%100% 的数据，1\le t \le 51≤t≤5，1\le n\le 10^51≤n≤10 5 ，0\le a_i\le 10^90≤a i ≤10 9 。，语言方向：C++，系统环境：Windows（462点数解答 | 2024-12-21 17:35:25）291
- 题目描述 给定一个长为 nn 的序列 a_1, a_2,a_3, \dots ,a_na 1 ,a 2 ,a 3 ,…,a n ，你需要执行 kk 次操作使这个序列为空。 每次操作可以执行下列内容之一： 选择两个数 i, ji,j，交换 a_i, a_ja i ,a j （需要满足 1 \le i < j \le n1≤i<j≤n）。 选择两个数 i, ji,j，删除 a_i,a_{i+1}, \dots ,a_ja i ,a i+1 ,…,a j （需要满足 1 \le i \le j \le n1≤i≤j≤n，且 a_i = a_ja i =a j ）。 请输出最小的操作数 kk。 输入格式 第一行输入一个正整数 tt（1 \le t \le 51≤t≤5），表示有 tt 个测试数据。 对于每个测试数据： 第一行输入一个正整数 nn（1 \le n \le 10^51≤n≤10 5 ），表示序列长度为 nn。 第二行输入 nn 个正整数 a_1,a_2 \dots a_na 1 ,a 2 …a n （0 \le a_i \le 10^90≤a i ≤10 9 ）。 输出格式 对于每个测试数据输出一个正整数 kk，表示最少的操作次数。 输入输出样例 输入 #1 复制 2 5 1 2 3 2 3 3 1000000000 1000000000 99999999 输出 #1 复制 2 2 说明/提示 数据范围 子任务 分值 限制 11 1010 n\le 3n≤3 22 2020 n\le 10n≤10 33 2020 a_i\le 2a i ≤2 44 1010 保证所有 a_ia i 相等 55 4040 - 对于 100\%100% 的数据，1\le t \le 51≤t≤5，1\le n\le 10^51≤n≤10 5 ，0\le a_i\le 10^90≤a i ≤10 9 。，语言方向：C++，系统环境：Windows（812点数解答 | 2024-12-21 17:36:14）350
- # 「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\（637点数解答 | 2024-12-21 14:56:50）212
- # 「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\（969点数解答 | 2024-12-21 14:56:57）225
- # 「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\（1279点数解答 | 2024-12-21 14:57:07）281
- # 「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\（2038点数解答 | 2024-12-21 14:57:39）248
- ## 题目背景 [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\（372点数解答 | 2024-12-21 15:27:24）142
- ## 题目背景 [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++（407点数解答 | 2024-12-21 15:27:41）212
- 题目背景 english statement. you must submit your code at the chinese version of the statement. 题目描述 给定一个长为 𝑛 n 的序列 𝑎 1 , 𝑎 2 , 𝑎 3 , … , 𝑎 𝑛 a 1 ,a 2 ,a 3 ,…,a n ，你需要执行 𝑘 k 次操作使这个序列为空。 每次操作可以执行下列内容之一： 选择两个数 𝑖 , 𝑗 i,j，交换 𝑎 𝑖 , 𝑎 𝑗 a i ,a j （需要满足 1 ≤ 𝑖 < 𝑗 ≤ 𝑛 1≤i<j≤n）。 选择两个数 𝑖 , 𝑗 i,j，删除 𝑎 𝑖 , 𝑎 𝑖 + 1 , … , 𝑎 𝑗 a i ,a i+1 ,…,a j （需要满足 1 ≤ 𝑖 ≤ 𝑗 ≤ 𝑛 1≤i≤j≤n，且 𝑎 𝑖 = 𝑎 𝑗 a i =a j ）。 请输出最小的操作数 𝑘 k。 输入格式 第一行输入一个正整数 𝑇 t（ 1 ≤ 𝑇 ≤ 5 1≤t≤5），表示有 𝑇 t 个测试数据。 对于每个测试数据： 第一行输入一个正整数 𝑛 n（ 1 ≤ 𝑛 ≤ 1 0 5 1≤n≤10 5 ），表示序列长度为 𝑛 n。 第二行输入 𝑛 n 个正整数 𝑎 1 , 𝑎 2 … 𝑎 𝑛 a 1 ,a 2 …a n （ 0 ≤ 𝑎 𝑖 ≤ 1 0 9 0≤a i ≤10 9 ）。 输出格式 对于每个测试数据输出一个正整数 𝑘 k，表示最少的操作次数。 输入输出样例 输入 #1复制 2 5 1 2 3 2 3 3 1000000000 1000000000 99999999 输出 #1复制 2 2 说明/提示 数据范围 子任务 分值 限制 1 1 10 10 𝑛 ≤ 3 n≤3 2 2 20 20 𝑛 ≤ 10 n≤10 3 3 20 20 𝑎 𝑖 ≤ 2 a i ≤2 4 4 10 10 保证所有 𝑎 𝑖 a i 相等 5 5 40 40 - 对于 100 % 100%，语言方向：C++，系统环境：Linux，代码风格：时间复杂度优先（331点数解答 | 2024-12-21 16:26:29）192
- # U397461 平衡划分 ## 题目描述 体育课一共有 $N$ 名同学，且同学们排成一队，每个同学都有一个体力值 $A_i$ 。 所以同学们可以被看做一个含有 $N$ 个正整数的序列 $A_1,A_2,\ldots,A_N$ 。 现在老师要带大家做游戏了，游戏需要分为把同学们分为三组，为了游戏的公平性，需要每组同学的体力值之和都完全一致， 并且每组组内的同学的位置要为连续的一段。 换句话说，你需要选择两个整数 $L,R$ ，使得 $A_1$ 到 $A_L-1$ 的和等于 $A_L$ 到 $A_R$ 的和 等于 $A_R+1$ 到 $A_N$ 的和 , $(2\le L \le R \le N-1)$ 请问老师能否完成一个公平的分组？ ## 输入格式 第一行一个正整数 $T$，表示数据组数。 对于每一组数据，第一行输入一个正整数 $N$，表示序列长度。 第二行输入 $N$ 个正整数 $A_1, A_2, \ldots, A_N$，含义见题面。 ## 输出格式 可以则输出`YES` ,否则输出`NO` ## 输入输出样例 #1 ### 输入 #1 ```（692点数解答 | 2025-06-18 19:19:39）70
- 题目描述 输入四个整数 x , y , a , b x,y,a,b，请你按照要求输出 x ∼ y x∼y 之间的所有数。 要求： 不要输出数字 a a。 不要输出大于等于数字 b b 的数。 输入格式 输入包括一行，包含四个整数 x , y , a , b x,y,a,b，数字之间用空格隔开。 输出格式 输出包括一行，为 x ∼ y x∼y 之间符合要求的数字。 input1 复制 10 20 13 17 output1 复制 10 11 12 14 15 16 input2 复制 50 55 52 100 output2 复制 50 51 53 54 55 样例解释 对于样例 1 1: 样例要求输出 10 ∼ 20 10∼20 之间不是 13 13, 且小于 17 17 的数，故有 10 , 11 , 12 , 14 , 15 , 16 10,11,12,14,15,16。 数据规模与约定 对于 100 % 100% 的数据， 1 ≤ x ≤ y ≤ 100 1≤x≤y≤100， x ≤ a ≤ y x≤a≤y, x ≤ b x≤b。 C++程序（138点数解答 | 2025-07-19 20:44:46）144
- # T614662 三元组 ## 题目描述 给定一个长度为$n$的整数数组$A$,求有多少个三元组$(i,j,k)$**同时满足**以下两个条件。 - $i \lt j \lt k$ - $A_i = A_j = A_k$ ## 输入格式 第一行包含一个整数$n$，表示数组长度。 第二行包含$n$个整数，表示数组$A$. ## 输出格式 输出一个整数，表示符合条件的三元组的数量。 ## 输入输出样例 #1 ### 输入 #1 ``` 12 4 1 5 4 1 1 4 1 5 4 1 1 ``` ### 输出 #1 ``` 24 ``` ## 说明/提示 对于$100\%$的数据,$3 \le n \le 10^6, -10^9 \le A_i \le 10^9$（606点数解答 | 2025-05-31 14:16:33）73