题解 | #灵梦的字符串问题#

灵梦的字符串问题

对于每一个元素，只有它小于等于下一个元素，复制它才可能会使得字符串变小。

把字符串通过双指针分成若干个子串，每个子串内元素相同。这样对于每一个字串而言，如果该字串的字符小于下一个子串的字符，那么对这个子串上的任意字符进行赋值操作都会使得字符串变小。我们可以把当前子串对应的进行排序，从小到大依次操作。

def solve(testcase):
    n, m = MI()
    s = I()
    A = LII()

    B = []
    l, r = 0, 0

    while r < n:
        while r < n and s[r] == s[l]:
            r += 1
        B.append((s[l], l, r - 1))
        l = r
    
    k = len(B)
    res = []

    for i in range(k - 1):
        pc, pl, pr = B[i]
        nc, nl, nr = B[i + 1]

        cnt = pr - pl + 1
        if pc < nc:
            C = sorted(A[pl: pr + 1])
            for c in C:
                if m >= c:
                    m -= c
                    cnt += 1
        res.append(pc * cnt)
    
    c, l, r = B[-1]
    res.append(c * (r - l + 1))

    print(''.join(res))


for testcase in range(1):
    solve(testcase)