蓝桥杯2024年第十五届省赛真题-封印宝石

在一次探险中，勇者小蓝发现了 n 颗闪烁着奇异光芒的宝石，每颗宝石都蕴含着魔法能量，分别记作 a1, a2, . . . , an。小蓝计划用 n 个特制的魔法盒子来封印这些宝石，防止其魔法能量被滥用。

封印宝石会消耗小蓝的体力，具体地，将第 i 颗宝石放入第 j 个盒子会消耗小蓝 i − j 点体力（注：需满足 j ≤ i 才能将第 i 颗宝石放入第 j 个盒子进行有效的封印）。小蓝也可以选择将魔法盒留空，以保存体力供后续使用。

此外，为了避免魔力相冲，每个盒子最多存放一颗宝石（每个宝石也只能放进一个盒子），且任意两个相邻盒子不能存放魔力值相同的宝石，相邻的盒子允许同时为空。小蓝初始的体力值为 k。在不超出体力限制的条件下，小蓝希望找出一种宝石的放置方法，使得宝石的魔力值在这 n 个盒子中的排列顺序具有最大的字典序（注：未放置宝石的盒子在此序列中记为 −1）。

作为勇者小蓝的追随者，请你帮他找出这一放置宝石的方法。

字典序的解释： 在本题中，字典序的大小是按照宝石的魔力值进行比较的。对于两个长度同为 L 的魔力值序列 a 和 b，如果存在一个位置 i，使得a_j = b_j 对所有 1 ≤ j < i 成立，但是 a_i < b_i，则序列 a 在字典序上小于序列 b。反之，如果 a_i > b_i，则序列 a 在字典序上大于序列 b。如果不存在这样的 i，则序列 a 和序列 b 的字典序相等。

输入的第一行包含两个整数 n 和 k ，用一个空格分隔，分别表示宝石的数量和小蓝的初始体力值。

第二行包含 n 个整数 a1, a2, · · · , an ，相邻整数之间使用一个空格分隔，分别表示每颗宝石的魔法能量值。

3 3
1 3 2

3 2 -1

【样例说明】

在开始放置宝石之前，体力为 3，宝石在盒子中的排列为 [−1, −1, −1]。1. 将第 2 个宝石放进第 1 个盒子，得到 [3, −1, −1]，体力剩余 2。2. 将第 3 个宝石放进第 2 个盒子，得到 [3, 2, −1]，体力剩余 1。最后宝石在盒子中的排列为 [3, 2, −1]。显然，没有比这更优的放置方法。

【评测用例规模与约定】

对于 20% 的评测用例，1 ≤ n ≤ 5 × 10³ ，0 ≤ k ≤ 3 × 10⁶ ，1 ≤ a_i ≤ 10⁵。对于所有评测用例，1 ≤ n ≤ 10⁵ ，0 ≤ k ≤ 10⁹ ，1 ≤ a_i ≤ 10⁹。