题解：B4274 [蓝桥杯青少年组省赛 2023] 数字游戏
前言
题目传送门
这么水的绿题，还可以写题解！
思路讲解
首先想到的肯定是暴力！
模拟这个过程，时间复杂度接近 \(O(n^2)\)，领取 TLE 大礼包。
然后我们考虑优化，发现对于一个数字，我们只需要知道它的值与数量即可，不需要知道它的位置。
因此，我们可以维护一个结构体数组记录一个数的值与其出现的次数，这样我们不需要一个一个的操作，能够大面积的操作。
时间复杂度就是 \(O(m)\)，注意 \(m\) 是有多少个不同的数字。
操作的时候用 \(l\) 和 \(r\) 分别表示左右边界，我们只需要遍历这个区间内的数字即可。
特别注意！！！
- 对于一个数字，加入它是最大值，操作后它并不是消失了，而是变成了次大值。
- 对于一个数字，加入它是最小值，操作后它并不是消失了，而是变成了次小值。
- 两种不同的操作是轮流进行的。
就是介么简单捏！
AC Code
注释版：
#include <bits/stdc++.h>
using namespace std;const int MAXN = 1e6 + 5; // 定义最大可能的数字范围int n; // 输入的数字个数
int a[MAXN]; // 存储输入的数字
int cur[MAXN]; // 统计每个数字出现的次数// 定义结构体，存储数字及其出现次数
struct node {int val; // 数字的值int num; // 该数字出现的次数
};
node cnt[MAXN]; // 存储所有数字及其出现次数（按值从小到大排序）int main() {// 输入阶段cin >> n;int l = 1, r = 0; // 双指针，l指向当前最小数字，r指向当前最大数字for (int i = 1; i <= n; i++) {cin >> a[i];cur[a[i]]++; // 统计每个数字出现的次数}// 预处理阶段：将统计结果存入cnt数组（自动按数字大小排序）for (int i = 1; i <= 1e6; i++) {if (cur[i]) { // 如果数字i出现过cnt[++r].val = i; // 存储数字icnt[r].num = cur[i]; // 存储数字i的出现次数}}long long ans = 0; // 记录总操作次数（可能很大，用long long）// 主循环：当数字种类 >=3 时继续操作while (r - l + 1 >= 3) {// 计算当前最小值和最大值的较小出现次数int sum = min(cnt[l].num, cnt[r].num);// 操作1：将最小值转化为次小值ans += sum; // 操作次数增加sumcnt[l].num -= sum; // 最小值减少sum次cnt[l + 1].num += sum; // 次小值增加sum次（因为最小值变成了次小值）// 如果最小值被消耗完，移动左指针if (!cnt[l].num) {l++; // 指向新的最小值// 检查剩余数字种类是否<=2if (r - l + 1 <= 2) {// 输出结果（注意：ans + sum - 1是因为最后一次操作可能未完成）cout << ans + sum - 1 << " " << cnt[l].val << " " << cnt[r].val << endl;return 0;}}// 操作2：将最大值转化为次大值ans += sum; // 操作次数增加sumcnt[r].num -= sum; // 最大值减少sum次cnt[r - 1].num += sum; // 次大值增加sum次（因为最大值变成了次大值）// 如果最大值被消耗完，移动右指针if (!cnt[r].num) {r--; // 指向新的最大值// 检查剩余数字种类是否<=2if (r - l + 1 <= 2) {// 输出结果cout << ans << " " << cnt[l].val << " " << cnt[r].val << endl;return 0;}}}return 0;
}
无注释版：
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 5;
int n;
int a[MAXN];
int cur[MAXN];
struct node
{int val, num;
};
node cnt[MAXN];
int main()
{cin >> n;int l = 1, r = 0;for (int i = 1; i <= n; i++){cin >> a[i];cur[a[i]]++;}for (int i = 1; i <= 1e6; i++){if (cur[i]){cnt[++r].val = i;cnt[r].num = cur[i];}}long long ans = 0;while (r - l + 1 >= 3){int sum = min(cnt[l].num, cnt[r].num);ans += sum;cnt[l].num -= sum;cnt[l + 1].num += sum;if (!cnt[l].num){l++;if (r - l + 1 <= 2){cout << ans + sum - 1 << " " << cnt[l].val << " " << cnt[r].val << endl;return 0;}}ans += sum;cnt[r].num -= sum;cnt[r - 1].num += sum;if (!cnt[r].num){r--;if (r - l + 1 <= 2){cout << ans << " " << cnt[l].val << " " << cnt[r].val << endl;return 0;}}}cout << ans << " " << cnt[l].val << " " << cnt[r].val << endl;return 0;
}