题解 | #牛牛的排序#

考察知识点：贪心

由题易知，最坏情况下也只需要 3 次排序即可，因此考虑 0 ~ 3 次排序的情况：

• 当数组本身有序时，不需要排序，输出 0；
• 当最大值或最小值已经就位时，只需要排序 1 次，输出 1；
• 当最大值与最小值都不在头尾时，需要排序 2 次，输出 2；
• 当最大值位于头部，最小值位于尾部时，需要排序 3 次，输出 3。

根据条件判断即可。

时间复杂度：$O(n)O(n)$

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

void solve()
{
    int n;
    cin >> n;
    vi a(n);
    for (int &i : a)
        cin >> i;
    int ma = *max_element(a.begin(), a.end());
    int mi = *min_element(a.begin(), a.end());
    bool flag = true;
    for (int i = 1; i < n; i++)
        if (a[i] < a[i - 1])
            flag = false;
    int ans = 2;
    if (flag)
        ans = 0;
    else if (a[0] == mi || a[n - 1] == ma)
        ans = 1;
    else if (a[0] == ma && a[n - 1] == mi)
        ans = 3;
    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}