CF1768B 题解

首先我们思考什么数是不用排序的。

显然，序列中一个由 \(1\) 开始，每次递增 \(1\) 的子序列是不用排序的。

为什么呢？

因为我们把其他数按从大到小排好后这个子序列刚好构成排好序后的数列的前缀。

因为当我们把除此以外的其他数字选出来后，这些数字构成排序后的数组的前缀，其他数字被后置到数组末尾构成后缀。

然后，假定有 \(m\) 个数不需要排序。那么每次可以排序 \(k\) 个数，故答案为 \((n-m)/k\) （需要上取整）。

#include<bits/stdc++.h>
//#define int long long
//#define lowbit(x) (x&-(x))
using namespace std;
const int maxn = 1e5+10;
int t;
int a[maxn];
void work(){
	int ans=0;
	stack<int> op;
	int n,k;
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	int now=0;
	for(int i=1;i<=n;i++){
		if(a[i]==now+1){
			now++;
		}
	}

	cout<<ceil((n-now)*1.0/k)<<'\n';
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--){
	work();
}

return 0;
}