这道题目不用写,因为必须要求用kotlin语言
讲一下我做这道题目的过程
我最开始正着想,如果\(k\)比较大的话,我们就想一次删的数少一点,所以考虑一次操作有哪些数被保留,于是我们发现,原序列的极大值点会被保留,于是一次操作被保留的数最多的情况就是如下的波浪形:
然后我们就发现正着想很难构造了,于是我们就倒着想:
最后一次删完了的序列是这样:$$[n]$$
我们考虑倒数第二次删完之后序列长成什么样,我们有个直觉就是越大的数越在后面被删除,于是我们考虑此时剩下的数是\(n-1\),也就是说序列此时是这样:$$[n-1,n]$$
那么对于倒数第三次,为了让上面两个数都不删除,我们必须要在中间插入\(n-2\),即$$[n-1,n-2,n]$$
这也就是正着想的时候,我们想要构造波浪形
同理第四次即$$[n-1,n-3,n-2,n-4,n]$$
在这样一直插入下去;如果说插入了\(1\)但是\(k\)次操作还没有用完,那么就是无解,否则的话,当\(k\)次操作用完的时候,我们将剩余的还没有插入的数,按照\([1,2,3,...]\)这样的顺序放在序列最前面即可
我们的构造方法与官方题解一样,但是官方题解的思路却跟我们完全不一样,但是是对我们的构造方法的严谨证明
标签:构造方法,着想,题解,Yet,插入,Another,序列,Constructive,我们 From: https://www.cnblogs.com/dingxingdi/p/18288766