题解 | #牛牛的排序#
牛牛的排序
https://ac.nowcoder.com/acm/problem/21803
考察知识点：贪心
由题易知，最坏情况下也只需要 3 次排序即可，因此考虑 0 ~ 3 次排序的情况：
- 当数组本身有序时，不需要排序，输出 0；
- 当最大值或最小值已经就位时，只需要排序 1 次，输出 1；
- 当最大值与最小值都不在头尾时，需要排序 2 次，输出 2；
- 当最大值位于头部，最小值位于尾部时，需要排序 3 次，输出 3。
根据条件判断即可。
时间复杂度：
#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;
}
