Moe's CF Life

喵~ 各位好呀！今天由我，你们最爱的小猫娘，来给大家讲解一道非常可爱的入门题：Codeforces 144A - Arrival of the General。别看是入门题，里面可是藏着一个小小的陷阱哦，就像藏在沙发垫下的小鱼干一样，得仔细找才能发现呢，嘻嘻~

题目大意

一位眼神不太好的将军要来视察士兵队列啦！将军的要求很简单：只要队伍里第一个士兵是最高的，最后一个士兵是最矮的，他就觉得这个队伍排得非常完美，喵~ （至于中间的士兵怎么样，他才不管呢！）

我们扮演的角色是可怜的团长，只有很短的时间来调整队伍。我们每次操作可以在一秒钟内交换任意两个相邻的士兵。

那么问题来了：要把一个乱糟糟的队伍，调整成将军喜欢的样子（最高个站最前，最矮个站最后），最少需要多少秒（也就是多少次交换）呢？

举个栗子：

(4, 3, 4, 2, 1, 1) 这个队列，将军就觉得很棒，因为最高的 4 在队首，最矮的 1 在队尾。
(4, 3, 1, 2, 2) 这个队列就不行，因为最矮的 1 不在队尾。

解题思路

要解决这个问题，我们其实只需要做两件事情，喵~

把一个身高最高的士兵移动到队伍的最前面（也就是索引为 0 的位置）。
把一个身高最矮的士兵移动到队伍的最后面（也就是索引为 n-1 的位置）。

因为每次只能交换相邻的士兵，所以把一个在 i 位置的士兵移动到 j 位置，最少需要 |i - j| 次交换。这就像猫猫我从沙发这头跑到那头，要一步一步地迈过去一样。

那么，我们来分别考虑这两件事：

第一步：移动最高的士兵

如果队伍里有多个身高最高的士兵，我们应该选哪一个移动呢？当然是选最省力气的那个啦！为了让移动到队首（索引 0）的交换次数最少，我们应该选择最靠前（索引最小）的那个最高士兵。把它移动到队首需要的交换次数，正好就是它当前的索引 max_idx。

第二步：移动最矮的士兵

同理，为了让移动到队尾（索引 n-1）的交换次数最少，我们应该选择最靠后（索引最大）的那个最矮士兵。把它移动到队尾需要的交换次数，就是 (n - 1) - min_idx。

把它们加起来就行了吗？

嗯... 差不多！总次数初步看来就是 max_idx + (n - 1 - min_idx)。但是，这里有个小小的陷阱哦！ฅ●ω●ฅ

注意这个特殊情况！

如果我们在遍历时找到的最靠前的最高士兵，它的位置（max_idx）恰好在最靠后的最矮士兵的位置（min_idx）的右边，也就是 max_idx > min_idx，会发生什么呢？

当我们把最高的士兵一步步往前移动的时候，它必然会经过最矮士兵原来的位置，并和它交换一次。这次交换，既让高个子离队首近了一步，也让矮个子离队尾近了一步！我们前面的计算方法，把这次交换的作用计算了两遍，相当于多算了一次。

所以，如果出现了 max_idx > min_idx 的情况，我们就要在总次数里减去 1，把重复计算的这次去掉。

总结一下思路就是：

一次遍历找到最靠前的最高士兵的索引 max_idx 和最靠后的最矮士兵的索引 min_idx。
计算总交换次数为 max_idx + (n - 1 - min_idx)。
如果 max_idx > min_idx，则将总次数减 1。
输出最终结果。

解题代码

下面是具体的实现代码，我已经加上了可爱的注释喵~

cpp

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

int main() {
    // 为了让输入输出更快一点，像猫猫冲刺一样！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    std::cin >> n;

    int max_val = 0;    // 用来记录当前找到的最高身高
    int max_idx = -1;   // 记录最靠前的最高士兵的位置
    int min_val = 101;  // 用来记录当前找到的最矮身高
    int min_idx = -1;   // 记录最靠后的最矮士兵的位置

    // 我们只需要遍历一遍数组就可以找到需要的信息啦
    for (int i = 0; i < n; ++i) {
        int height;
        std::cin >> height;

        // 找最靠前的最高士兵
        // 只有当身高严格大于当前最大值时才更新
        // 这样就能保证 max_idx 是第一个最大值的位置
        if (height > max_val) {
            max_val = height;
            max_idx = i;
        }

        // 找最靠后的最矮士兵
        // 当身高小于或等于当前最小值时就更新
        // 这样就能保证 min_idx 是最后一个最小值的位置
        if (height <= min_val) {
            min_val = height;
            min_idx = i;
        }
    }

    // 把最高个移动到队首需要的步数
    int swaps_to_front = max_idx;
    // 把最矮个移动到队尾需要的步数
    int swaps_to_back = (n - 1) - min_idx;

    int total_swaps = swaps_to_front + swaps_to_back;

    // 这里就是那个小陷阱！喵~
    // 如果最高个在最矮个的右边，移动时会“顺路”帮最矮个移动一次
    // 我们多算了一次，要减掉
    if (max_idx > min_idx) {
        total_swaps--;
    }

    std::cout << total_swaps << std::endl;

    return 0;
}

知识点介绍

这道题虽然简单，但也涉及了几个重要的编程思想哦。

贪心算法 (Greedy Algorithm) 贪心算法就是每一步都做出当前看起来最好的选择，期望最终能得到全局最优解。在这道题里，我们的“贪心”体现在：
- 要移动最高士兵到队首，我们贪心地选择了最靠前的那个，因为它移动步数最少。
- 要移动最矮士兵到队尾，我们贪心地选择了最靠后的那个，因为它移动步数也最少。幸运的是，在这个问题里，这种贪心策略是正确的，喵~ 就像猫猫总是先吃离得最近的小鱼干一样，这样最省力气！
数组遍历与索引 这是最基础的操作啦。我们需要熟练地遍历一个数组，并且清楚地知道每个元素的值和它的索引。这道题的核心就是找到特定值的索引。
边界情况与细节处理 (Edge Case) 编程不仅仅是实现主要逻辑，更重要的是处理好各种特殊情况。max_idx > min_idx 就是本题的关键细节。在写代码时，要像猫猫走路一样小心翼翼，思考各种可能的情况，不能忽略任何一个小角落哦！

好啦，这次的题解就到这里啦！希望能帮助到你，现在将军满意了，我也可以去阳台晒太阳睡午觉了，喵~ 下次再见！( ´ ▽ ` )ﾉ

题目大意 ​

解题思路 ​

解题代码 ​

知识点介绍 ​

题目大意

解题思路

解题代码

知识点介绍