/* 多多有一个长度为n的数组,依次采用如下策略对数组从小到大进行排序 1.将数组划分为k个非空子串(每个子串为原数组中连续数字组成的子序列) 2.调整k个子串的顺序,每个子串内元素顺序不变 3.将k个子串首尾相连,组成一个新的数组 以上策略不保证最终得到的数组有(单调递增)请你计算一下,对于给定的数组与划分数k,能否最终得到一个有序递增的序列 输入描述: 第一行一个数字T(T < 5),代表测试用例个数 对于每组测试用例:第一行两个数字:n,k,代表数组长度与划分子串个数,0 using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(0); int T; cin >> T; while(T--){ long long n, k; cin >> n >> k; vector arr(n); for(auto &x : arr)cin >> x; //Create a vector of pairs(value, original index) vector> sorted_arr(n); for(long long i = 0; i < n; i++){ sorted_arr[i] = {arr[i], i+1};//1-based indexing } // Sort the array based on values sort(sorted_arr.begin(), sorted_arr.end()); // Count the number of blocks where indices are consecutive long long m = 1;// At least one block for(long long i = 1; i < n; i++){ if(sorted_arr[i].second != sorted_arr[i-1].second +1){ m++; } } // If number of blocks <=k, it's possible if(m <= k){ cout <<"True\n"; } else{ cout<<"False\n"; } } }