灵梦的字符串问题时间限制1秒 空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述你这家伙是杀人犯呢。——蕾米莉亚·斯卡蕾特一个人的话又不是大量屠杀所以没关系。——博丽灵梦退治完妖怪灵梦从红魔馆抢来一个字符串。这是一个长度为n nn仅由小写字母构成的字符串s ss下标从1 11开始。灵梦有m mm点灵力计划消耗灵力对字符串进行至多一次修改操作使最终得到的字符串最小。操作分为两步第一步从字符串s ss中选取若干位置。对于每个被选中的位置i ii需要消耗a i a_iai​​ 点灵力。第二步对于每个选中的位置将对应字符复制一次新复制的字符紧接原字符之后插入。例如对于字符串s a b b c a sabbcasabbca我们已经选中了橙色的两个位置复制操作后得到s ′ a b b b c a a s′abbbcaas′abbbcaa。灵梦的灵力值有限所以她希望你帮她计算出在消耗灵力值不超过m mm的情况下最后能够得到的字典序最小的字符串是什么。从字符串的第一个字符开始逐个比较直至发现第一个不同的位置比较这个位置字符的字母表顺序字母序较小的字符串字典序也较小如果比较到其中一个字符串的结尾时依旧全部相同则较短的字符串字典序更小。输入描述第一行输入两个整数n , m ( 1 ≦ n ≦ 2 × 10 5 ; 1 ≦ m ≦ 10 18 ) n,m(1≦n≦2×10^5; 1≦m≦10^{18})n,m(1≦n≦2×105;1≦m≦1018)代表字符串的长度、灵梦的灵力值。第二行输入一个长度为n nn仅有小写字母构成的字符串s ss。第三行输入n nn个整数a 1 , a 2 , … , a n ( 1 ≦ a i ≦ 10 9 ) a_1,a_2,…,a_n(1≦a_i≦10^9)a1​,a2​,…,an​(1≦ai​≦109)其中第i ii个整数a i a_iai​​ 代表选中位置i ii需要消耗的灵力值。输出描述输出一个字符串代表最后能够得到的字典序最小的字符串。示例1输入3 1 aba 1 1 1输出aaba说明在这个样例中一共有三种不同的选择方案选中第1 11个位置消耗1 11点灵力得到s ′ a a b a s′aabas′aaba选中第2 22个位置消耗1 11点灵力得到s ′ a b b a s′abbas′abba选中第3 33个位置消耗1 11点灵力得到s ′ a b a a s′abaas′abaa。显然最后能够得到的字典序最小的字符串是 a a b a aabaaaba。示例2输入7 10 aabacaa 3 3 3 2 1 2 1输出aaaabaacaa解题思路本题核心是贪心策略结合分块处理利用字典序“左位优先级最高”的特性从左到右优化字符串在灵力限制下得到最小字典序。首先将字符串划分为连续相同字符的块基于字典序性质分析复制操作的收益若当前块是最后一块或下一块字符小于当前字符复制当前字符会让字典序变大——末尾复制会使字符串变长等前缀下短串字典序更小下一块字符更小时复制会推迟小字符的出现。因此这类块不进行任何复制直接保留原长度。若下一块字符大于当前字符复制当前字符可以延长小字符的连续长度推迟大字符出现能有效减小字典序。此时将块内所有位置的消耗从小到大排序在剩余灵力范围内优先选择消耗最低的位置复制尽可能增加当前块的长度最大化字典序优化效果。按上述规则从左到右处理所有块最终拼接各块得到答案。算法总时间复杂度为O ( n log ⁡ n ) O(n\log n)O(nlogn)分块线性遍历 各块内排序总和不超过全排序完全适配n ≤ 2 × 10 5 n \le 2\times10^5n≤2×105的数据约束。总结核心逻辑按连续相同字符分块从左到右贪心处理仅对“后接更大字符”的块执行复制操作优先选低成本位置最大化复制数量。关键操作字符串分块、判断复制收益、消耗排序贪心选取、拼接结果字符串。效率保障单遍分块 局部排序无冗余运算线性为主的复杂度轻松处理十万级字符串。代码简要说明分块遍历用双指针l和r定位连续相同字符的块cnt记录块的初始长度。收益判断非末尾块且下一块字符更大时进入复制优化流程否则直接保留原长度。贪心复制提取当前块内所有位置的消耗值并升序排序从小到大依次尝试复制灵力足够则增加块长度并扣除消耗直到灵力不足或全部复制完毕。结果拼接将处理后的当前块字符追加到答案字符串移动指针处理下一个块最终输出完整结果。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;voidsolve(){ll n,m;cinnm;string s;cins;vectorlla(n);for(ll i0;in;i)cina[i];string ans;ll l0;while(ln){ll rl;while(rns[r]s[l])r;ll cntr-l;if(rns[l]s[r]){vectorllc;for(ll il;ir;i)c.push_back(a[i]);sort(c.begin(),c.end());for(ll x:c){if(mx){m-x;cnt;}elsebreak;}}ans.append(cnt,s[l]);lr;}coutans\n;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll t1;while(t--)solve();return0;}