解题思路
需要构造一个长度为 L 的排列 p1,p2,…,pL,使其恰好有 K 个跃升点。
跃升点的定义为:对于 i≥3,若 pi≥max(pi−2,pi−1),则 i 是一个跃升点。
观察发现,如果排列的前一段是严格递增的,那么从第 3 个位置开始,每个新加入的数都会大于它前面两个数,从而形成跃升点。具体地:
- 取 K+2 个连续递增的数放在排列的最前面,这些数从第 3 个位置到第 K+2 个位置一共会形成 K 个跃升点。
- 剩下的 L−(K+2) 个数如果按严格递减顺序排列,它们会逐渐变小,不会再超过前两个较大的数,因此不会产生新的跃升点。