You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
68 lines
2.1 KiB
68 lines
2.1 KiB
/*
|
|
多多有一个长度为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";
|
|
}
|
|
}
|
|
}
|