{"problem":{"name":"[蓝桥杯 2024 省 A] 封印宝石","description":{"content":"在一次探险中，勇者小蓝发现了 $n$ 颗闪烁着奇异光芒的宝石，每颗宝石都蕴含着魔法能量，分别记作 $a_1, a_2,\\cdots, a_n$。小蓝计划用 $n$ 个特制的魔法盒子来封 印这些宝石，防止其魔法能量被滥用。   封印宝石会消耗小蓝的体力，具体地，将第 $i$ 颗宝石放入第 $j$ 个盒子会消耗小蓝 $i - j$ 点体力（注：需满足 $j ≤ i$ 才能将第 $i$ 颗宝石放入第 $","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10392"},"statements":[{"statement_type":"Markdown","content":"在一次探险中，勇者小蓝发现了 $n$ 颗闪烁着奇异光芒的宝石，每颗宝石都蕴含着魔法能量，分别记作 $a_1, a_2,\\cdots, a_n$。小蓝计划用 $n$ 个特制的魔法盒子来封\n印这些宝石，防止其魔法能量被滥用。  \n封印宝石会消耗小蓝的体力，具体地，将第 $i$ 颗宝石放入第 $j$ 个盒子会消耗小蓝 $i - j$ 点体力（注：需满足 $j ≤ i$ 才能将第 $i$ 颗宝石放入第 $j$ 个盒子进行有效的封印）。小蓝也可以选择将魔法盒留空，以保存体力供后续使用。  \n此外，为了避免魔力相冲，每个盒子最多存放一颗宝石（每个宝石也只能放进一个盒子），且任意两个相邻盒子不能存放魔力值相同的宝石，相邻的盒子允许同时为空。  \n小蓝初始的体力值为 $k$。在不超出体力限制的条件下，小蓝希望找出一种宝石的放置方法，使得宝石的魔力值在这 $n$ 个盒子中的排列顺序具有最大的字典序（注：未放置宝石的盒子在此序列中记为 $-1$）。  \n作为勇者小蓝的追随者，请你帮他找出这一放置宝石的方法。  \n\n**字典序的解释**： 在本题中，字典序的大小是按照宝石的魔力值进行比较的。对于两个长度同为 $L$ 的魔力值序列 $a$ 和 $b$，如果存在一个位置 $i$，使得 $a_j = b_j$ 对所有 $1 ≤ j < i$ 成立，但是 $a_i < b_i$，则序列 $a$ 在字典序上小于序列 $b$。  \n反之，如果 $a_i > b_i$，则序列 $a$ 在字典序上大于序列 $b$。如果不存在这样的 $i$，则序列 $a$ 和序列 $b$ 的字典序相等。\n\n## Input\n\n输入的第一行包含两个整数 $n$ 和 $k $，用一个空格分隔，分别表示宝石的数量和小蓝的初始体力值。  \n第二行包含 $n$ 个整数 $a_1, a_2,\\cdots , a_n $，相邻整数之间使用一个空格分隔，分别表示每颗宝石的魔法能量值。\n\n## Output\n\n输出一行包含 $n$ 个整数，相邻整数之间使用一个空格分隔，表示每个魔法盒中宝石的魔法能量值。如果某个魔法盒为空，则对应位置输出 $-1$。\n\n[samples]\n\n## Note\n\n在开始放置宝石之前，体力为 $3$，宝石在盒子中的排列为 $[-1, -1, -1]$。  \n1. 将第 $2$ 个宝石放进第 $1$ 个盒子，得到 $[3, -1, -1]$，体力剩余 $2$。\n2. 将第 $3$ 个宝石放进第 $2$ 个盒子，得到 $[3, 2, -1]$，体力剩余 $1$。  \n\n最后宝石在盒子中的排列为 $[3, 2, −1]$。显然，没有比这更优的放置方法。\n\n对于 $20\\%$ 的评测用例，$1 ≤ n ≤ 5 × 10^3 ，0 ≤ k ≤ 3 × 10^6 ，1 ≤ a_i ≤ 10^5$。  \n对于所有评测用例，$1 ≤ n ≤ 10^5 ，0 ≤ k ≤ 10^9 ，1 ≤ a_i ≤ 10^9$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10392","tags":["贪心","线段树","2024","蓝桥杯省赛"],"sample_group":[["3 3\n1 3 2","3 2 -1"]],"created_at":"2026-03-03 11:09:25"}}