题目描述
- 将数组精确拆分为非空子数组,这样每个元素都只属于一个子数组。
- 任意重新排序这些子数组。
- 按新顺序合并子数组。
样例
input
3
5 4
6 3 4 2 1
4 2
1 -4 0 -2
5 1
1 2 3 4 5
output
Yes
No
Yes
在第一个测试用例中, a = [ 6 , 3 , 4 , 2 , 1 ],和 k = 4,所以我们可以进行如下操作:
拆分 一个 进入 { [ 6 ] , [ 3 , 4 ] , [ 2 ] , [ 1 ] }.
对它们重新排序: { [ 1 ] , [ 2 ] , [ 3 , 4 ] , [ 6 ] }.
合并它们: [ 1 , 2 , 3 , 4 , 6 ],所以现在数组已排序。
在第二个测试用例中,无法通过将数组拆分为仅对数组进行排序 2 子阵列。
举个例子,如果我们把它分成 { [ 1 , − 4 ] , [ 0 , − 2 ] },
我们可以将它们重新排序为 { [ 1 , − 4 ] , [ 0 , − 2 ] } 或 { [ 0 , − 2 ] , [ 1 , − 4 ] }.
但是,合并子数组后,就不可能得到一个有序的数组。
算法1
(离散化+贪心) $O(n)$
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 200010;
int a[N], b[N];
int T, n, m;
void slove()
{
int cnt = 0, k = 0;
cin >> n >> m;
for (int i = 1; i <= n; i ++) cin >> a[i], b[i] = a[i];
// 排序
sort(b+1, b+n+1);
// 二分找到不小于他的最小数 离散化
for (int i = 1; i <= n; i ++) a[i] = lower_bound(b+1,b+n+1,a[i]) - b;
for (int i = 1; i <= n; i ++)
{
cnt ++;
while (i < n && a[i]+1 == a[i+1]) i ++;
}
if (cnt <= m) puts("Yes");
else puts("No");
}
int main()
{
cin >> T;
while (T --)
{
slove();
}
return 0;
}
eturn 0;
}