自动搬运

查看原文

来自洛谷，原作者为

	Yxa_Sheep 打表过样例，暴力出奇迹，搜索真牛逼，骗分进省一||深搜 MLE，广搜 TLE，打表 RE，退火又 CE||删掉 display 看主页||被封取关（解封后私信）||六年级蒟蒻 ，代词请用“他”||当前状态：<离线>

搬运于2025-08-24 21:18:16，当前版本为作者最后更新于2025-06-16 11:17:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

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

思路

一开始我用模拟，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;
}

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