题解：B4274 [蓝桥杯青少年组省赛 2023] 数字游戏

· · 题解

题意

操作一：将最大值变成次大值，操作二：将最小值变成次小值。重复执行这两个操作，直到只剩两个不同数字。

思路

一开始我用模拟，TLE 了，30。然后在 dalao 的提示下想到先用结构体存储每个数组出现的次数，然后在一次清空所有最大值与最小值。首先将每个数出现的次数存入 book 数组（和桶排序差不多），然后用一个结构体存储每个数组和他的出现次数，把 book 数组的内容转移过来，方便查找。用 x 表示结构体中第一个数字的下标，用 y 表示结构体中最后一个数字的下标，每次清空的时候就把 x 向后移一项或者把 y 向前移一项，直到只剩下 x 所指向的数和 y 所指向的数就可以结束并输出答案了。细节看代码。

代码

#include <bits/stdc++.h>
using namespace std;
int n, x = 1, y, k, book[1000010];//x为结构体a的起始位置(1),y为结构体的结束位置(长度)
long long ans;
struct node { int num, cnt; } a[1000010];//num存储这个数字,cnt存储这个数字出现的次数
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &k), book[k]++;//数字k的出现次数加1
    for (int i = 1; i <= 1000000; i++)
        if (book[i])
            a[++y].num = i, a[y].cnt = book[i];//将book数组里的数据移到a里，在无形中排好序了
    while (y - x + 1 > 2)//如果a的长度(不同数字)大于2就继续
    {
        k = min(a[x].cnt, a[y].cnt);
        a[x].cnt -= k, a[x + 1].cnt += k, ans += k;//一次减去k个数，这里注意最小值减k个，而次小值要加k个，因为最小值变成次小值了
        if (!a[x].cnt)//如果最小值被减完了
        {
            x++;//移到下一位(原来的次小值)
            if (y - x + 1 <= 2)//如果a的长度(不同数组)小于等于2
            {
                printf("%lld %d %d", ans + k - 1, a[x].num, a[y].num);//输出答案，这里ans要加k减1，因为操作一和操作二是交替进行的
                return 0;//完美结束
            }
        }
        a[y].cnt -= k, a[y - 1].cnt += k, ans += k;//最大值的数量也减去k个
        if (!a[y].cnt)//如果最小值被减完了(原来的次大值)
        {
            y--;//移到前一位
            if (y - x + 1 <= 2)
            {
                printf("%lld %d %d", ans, a[x].num, a[y].num);//输出答案
                return 0;//完美结束
            }
        }
    }
    return 0;
}

完结!!!题解来之不易，且看且珍惜。