P7957 [COCI2014-15#6] KRATKI 题解
Naro_Ahgnay
·
·
题解
题目描述
给定数列的长度 n。
你需要构造出一个 n 的排列，使得它的 LMS（最长单调子序列） 长度为 k。
如果无解，输出 \texttt{-1}。
注意：因为是严格递增，所以该序列中不能出现重复的数。
思路
首先考虑什么时候无解。显然的结论：
当 k^2<n 时，该问题无解。
证明：
对于该序列中的任意一个数 a，当 k^2<n 时，此时 n-\lfloor \frac{n}{k} \rfloor \times k >0，在对前面 k 组数进行构造时，最后剩下的数必然会让最长单调子序列的长度大于 k。
例子：
前面两个数无论填1还是2还是3，后面那个数必然会让最长单调子序列的长度大于1。此时直接输出 $-1$ 就行。
对于有解的情况，我们只需要构造两个严格上升序列（当然严格下降序列也行），且保证前面的严格上升序列的最小值大于后面的严格上升序列的最大值就行了。可以使前面序列从 $1+n-m$ 开始一直到 $m$，后面序列从 $1$ 开始一直到 $n-m$。
### code:
```cpp
#include<bits/stdc++.h>
using namespace std;
long long n,m;
int main()
{
scanf("%lld%lld",&n,&m);
if(m*m<n)
{
puts("-1");
return 0;
}
for(long long i=1;i<=m;i++)
printf("%lld ",i+n-m);
for(long long i=m+1;i<=n;i++)
printf("%lld ",i-m);
return 0;
}
```