正经题解｜新年排列

题面大意

给你一个长度为$n$的全排列$p$，和一个整数$k$，每次可以任意选择$k$个元素，以升序移动到$p$的末尾，直到$p$为升序。

题意分析

求最小操作次数，使得$p$变为升序

解题思路

找到以1开头的最长上升序子序列$q$，那么不属于$q$部分的则都要移动，将非$q$部分的元素移动到$p$的尾部就好。

时间复杂度解析

我们只需要遍历一次$p$序列，就能找到子序列$q$，复杂度为$O(n)$。

代码演示

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N];
int main() {
    int n,k;
    cin >> n >> k;
    int j = 0;
    for(int i=0;i<n;i++) {
        cin >> a[i];
        if (a[i] == 1) j = i + 1;
    }
    int l = 1, len = 1;
    for(;j<n;j++) {
        if (a[j] == l + 1) {
            l = l + 1;
            len++;
        }
    }
    cout << (n - len) / k + ( (n - len) % k > 0)<< endl;
    return 0;
}