code/PinDD/test.cpp

/*
多多有一个长度为n的数组，依次采用如下策略对数组从小到大进行排序
1.将数组划分为k个非空子串(每个子串为原数组中连续数字组成的子序列)
2.调整k个子串的顺序，每个子串内元素顺序不变
3.将k个子串首尾相连，组成一个新的数组

以上策略不保证最终得到的数组有(单调递增)请你计算一下，对于给定的数组与划分数k，能否最终得到一个有序递增的序列

输入描述：
第一行一个数字T(T < 5)，代表测试用例个数
对于每组测试用例:第一行两个数字:n,k，代表数组长度与划分子串个数，0<k<n<1e5
第二行n个数字a1,a2,…,an，0≤|ai|;≤ 1e14，保证数组内元素各不相同

输出描述：
对于每个测试用例，如果能够得到有序序列，输出“Tue"(不含引号)，否则输出“False(不含引号)

示例：
输入：
3
5 3
8 12 7 -6 5
4 2
2 3 -6 4
5 5
10 6 8 -5 -10
输出：
True
False
True

思路 排序的同时也对原来的需要排序，然后判断块应该分割的次数，如果小于等于K则可以
*/

#include <bits/stdc++.h>
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<long long> arr(n);
        for(auto &x : arr)cin >> x;
        //Create a vector of pairs(value, original index)
        vector<pair<long long, long long>> 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";
        }
    }
}