Codeforces 259B Little Pony and Sort by Shift：循環移位排序

題目大意

給定長度 n（≤ 10⁵）的整數序列，允許操作：將最後一個元素移到最前面（右循環移位 1 位）。求最少操作次數使序列非遞減，不可能則輸出 −1。

關鍵觀察

序列經過 k 次操作後等價於原序列循環右移 k 位。
若存在排序後的非遞減序列，則原序列必須是某個非遞減序列的循環移位。
即原序列中「降序對」a[i] > a[i+1] 的個數至多為 1。

判斷邏輯

1. 統計 cnt = |{ i | a[i] > a[i+1] }|（i 從 0 到 n−2）。
2. 若 cnt = 0：已有序，答案 0。
3. 若 cnt = 1 且 a[n−1] ≤ a[0]：答案 = n − pos − 1，其中 pos 是唯一降序對的位置 i。
4. 否則答案 −1。

完整代碼

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n; 
    while (cin >> n) {
        vector<int> a(n);
        for (int &x : a) cin >> x;
        int cnt = 0, pos = -1;
        for (int i = 0; i < n - 1; ++i)
            if (a[i] > a[i + 1]) { ++cnt; pos = i; }
        if (cnt == 0) cout << 0 << '\n';
        else if (cnt == 1 && a[n - 1] <= a[0])
            cout << n - pos - 1 << '\n';
        else
            cout << -1 << '\n';
    }
    return 0;
}

複雜度

O(n) 時間，O(n) 空間。