题解 | 小Q的排序

#include <iostream>
#include <vector>

int main() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    int min_index = 0, max_index = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] < a[min_index]) {
            min_index = i;
        }
        if (a[i] > a[max_index]) {
            max_index = i;
        }
    }
    if (min_index == 0 && max_index == n - 1) {
        std::cout << 0 << std::endl;
    } else if (min_index == 0) {
        std::cout << 1 << std::endl;
    } else if (max_index == n - 1) {
        std::cout << 1 << std::endl;
    } else if (min_index == n - 1 && max_index == 0) {
        std::cout << 3 << std::endl;
    } else {
        std::cout << 2 << std::endl;
    }
}
// 64 位输出请用 printf("%lld")

解题思路：

观察可得，有四种情况。第一种：原数组就是按升序排的，操作次数为0；第二种：最大的在末端或最小的在开头，以及最大的在末端并且最小的在开头，操作次数为1；第三种：原数组按降序排的，操作次数为3；第四种：其他的情况，操作数为2。

怎么来讨论的话，就可以先分别找到原数组最小数和最大数的下标，然后就可以对比各下标符合哪种情况了。