需要构造一个长度为 L 的排列 p1,p2,…,pL,使其恰好有 K 个跃升点。
跃升点的定义为:对于 i≥3,若 pi≥max(pi−2,pi−1),则 i 是一个跃升点。
观察发现,如果排列的前一段是严格递增的,那么从第 3 个位置开始,每个新加入的数都会大于它前面两个数,从而形成跃升点。具体地:
给定一个长度为 L 的排列 p1,p2,…,pL,对于 i≥3,若满足 pi≥max(pi−2,pi−1),则称位置 i 为一个“跃升点”。
请构造一个长度为 L 的排列,使得跃升点的个数恰好为 K。如果有多种可能的构造,输出任意一种即可。
约束条件:测试用例总数 T 不超过 105,每个测试用例的长度 L 满足 3≤L≤2×105,跃升点个数 K 满足 0≤K≤L−2。所有测试用例的 L 之和不超过 2×105。
第一行包含一个整数 T,表示测试数据组数。
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册