Moe's CF Life

喵哈~！主人，欢迎来到我的题解小站！今天我们要看的是一道叫做 "Too Min Too Max" 的有趣问题，编号是 1934A 哦。这道题就像逗猫棒一样，看起来晃来晃去很复杂，但只要找到诀窍，一下子就能抓住啦！嘻嘻~

下面就让本猫娘带你一步步解开这道题的谜题吧！ฅ'ω'ฅ

题目大意

这道题是说呀，给我们一个有 n 个整数的数组 a。我们需要从里面选出四个不同的下标 i, j, k, l，然后计算下面这个表达式的值：

|a_i - a_j| + |a_j - a_k| + |a_k - a_l| + |a_l - a_i|

我们的任务就是，找到一种选择 i, j, k, l 的方法，让这个表达式的值变得最大！然后把这个最大值告诉人家就好啦~

简单来说，就是在 n 个数里选 4 个数，让它们按某种顺序连接成的“环路”的总长度最长。

解题思路

我们要让这个总路程最大，应该怎么选这四个点，又应该按什么顺序跑呢？

第一步：选哪四个点？

为了让距离和最大，我们肯定希望选的点尽可能地分散开，对不对？就像猫猫伸懒腰，要伸展到最长！所以，一个很自然的想法就是，去数组的“两端”——也就是最大值和最小值附近去找。

直觉告诉我们，选择数组里最大、第二大、最小和第二小的这四个数，最有可能得到最优解。因为它们构成了数组中最分散的四个点。

第二步：怎么排列顺序？

好啦，我们选定了四个数，假设它们从小到大分别是 min1, min2, max2, max1。现在要决定 i, j, k, l 对应的是哪一个了。这四个点在数轴上形成一个环路，要让总长度最大，我们应该在它们之间来回跳跃，而不是顺着走。

想象一下，这四个点在数轴上排成一排：min1 ... min2 ... max2 ... max1

如果顺着走：比如 min1 -> min2 -> max2 -> max1 -> min1。总路程是 (min2-min1) + (max2-min2) + (max1-max2) + (max1-min1) = 2 * (max1 - min1)。
如果交叉走：比如 min1 -> max1 -> min2 -> max2 -> min1。总路程是 |min1 - max1| + |max1 - min2| + |min2 - max2| + |max2 - min1|。因为我们已经知道大小关系 min1 <= min2 <= max2 <= max1，所以可以去掉绝对值符号： = (max1 - min1) + (max1 - min2) + (max2 - min2) + (max2 - min1)= 2 * (max1 - min1) + 2 * (max2 - min2)

比较一下两种走法，很明显，第二种交叉走（或者叫“之”字形走）得到的路程更长呀！2 * (max2 - min2) 是一个非负数，所以第二种走法的结果肯定不会比第一种小。

所以，我们的策略就确定下来啦：

先把数组 a 从小到大排个序。
找出最小的数 a[0] (min1)，第二小的数 a[1] (min2)，第二大的数 a[n-2] (max2)，和最大的数 a[n-1] (max1)。
计算 (max1 - min1) + (max1 - min2) + (max2 - min1) + (max2 - min2) 的值，这就是答案啦！

这个方法是不是很简单喵~？

题解代码

下面是具体的实现代码，本猫娘加了一些注释，方便主人理解哦~

cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

void solve() {
    int n;
    std::cin >> n;
    std::vector<long long> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }

    // 第一步：将数组排序，方便我们找到最大和最小的元素，喵~
    std::sort(a.begin(), a.end());

    // 第二步：挑出我们需要的四个关键先生！
    // 最小的, a[0]
    long long min1 = a[0];
    // 第二小的, a[1]
    long long min2 = a[1];
    // 第二大的, a[n-2]
    long long max2 = a[n - 2];
    // 最大的, a[n-1]
    long long max1 = a[n - 1];

    // 第三步：按照我们分析出的最优“交叉”路径计算总距离
    // 这个路径可以看作是 max1 -> min1 -> max2 -> min2 -> max1
    // |max1 - min1| = max1 - min1
    // |min1 - max2| = max2 - min1
    // |max2 - min2| = max2 - min2
    // |min2 - max1| = max1 - min2
    // 把它们加起来就是最终的答案啦！
    long long result = (max1 - min1) + (max2 - min1) + (max1 - min2) + (max2 - min2);

    std::cout << result << std::endl;
}

int main() {
    // 加速一下输入输出，让程序跑得像猫一样快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

知识点小课堂

嘻嘻，解决问题之后，来补充一点点知识吧，这样下次遇到类似的问题就不会怕啦！

绝对值与距离：|x - y| 在几何上代表数轴上点 x 和点 y 之间的距离。理解这一点是解决很多这类问题的基础哦。
贪心思想 (Greedy Approach)：我们的解法就是一种贪心。每一步都做出当前看起来最好的选择。我们想要距离和最大，就贪心地选择了最分散的四个点（最大、第二大、最小、第二小），最终证明这个选择就是全局最优的。贪心虽然不总是对的，但在这道题里它完美地生效了！
排序 (Sorting)：排序是算法竞赛中的家常便饭，就像猫猫每天都要梳理毛发一样！通过排序，我们可以轻松地获取到数组的极值、中位数等信息，让混乱的数据变得井井有条，大大简化问题。
排列组合分析：虽然这道题我们没有用暴力法，但分析的过程其实蕴含了组合的思想。我们分析了四个点的不同排列（环路）方式，并找到了最优的那一种。这告诉我们，当问题规模不大时，可以先分析小规模的情况来寻找规律。

好啦，这次的题解就到这里结束啦！希望本猫娘的讲解对主人有帮助哦~ 如果还有什么问题，随时可以再来问我！喵~ ( ´ ▽ ` )ﾉ

题目大意 ​

解题思路 ​

第一步：选哪四个点？ ​

第二步：怎么排列顺序？ ​

题解代码 ​

知识点小课堂 ​