给定一串桶（字母）。找出将所有水桶带到底部的成本（可能是最小的）

Question

Bob 是一名建筑工人，他通过数学来提高效率。他在一个工地上工作，有 n 桶水泥，上面标有不同的字符 (a - z)。他有学长的严格命令，不能改变桶的顺序。

在开始他的工作之前，他得到了一个长度为 n 的字符串 s，其中位置 [=38= 的字符]i (1 <= i <= n) 给我们第 i'th 个桶上的标记。他一次只能提一个水桶，带回基地。在每一轮中，他都有一个关于拿起哪个桶的标准。他将拿取标有最小字符 (a

约束条件

1 < t,m < 10^5

所有测试用例n的总和不超过10^6

样本输入

2
badce

样本输出

7

说明

badce - 首先，Bob 拿走标记为 'a' 的第二个篮子，并将成本加 2。
bdce - 然后他拿走第一个标记为 'b' 的篮子，并将成本加 1。
dce - 然后他拿下第二个标记为 'c' 的篮子，并将成本加 2。
de - 他再次拿起标记为 'd' 的第一个篮子，并将成本加 1。
e - 他再次拿起标记为 'e' 的第一个篮子，并将成本加 1。

总成本变为 7 个单位。

我尝试在 Python 中编写代码，但在某些情况下给出 TLE。这是我的方法-->

n = int(input())
s = input()
count_array = [0] * 26
for i in range(n):
    count_array[ord(s[i])-97] += 1

alphabets = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
    
ans = 0

for i in range(26):
    while count_array[i] > 0:
       idx = s.index(alphabets[i])
       ans += idx + 1
       if idx > -1: s = s[0:idx] + s[idx+1:]
       count_array[i] -= 1
    
print(ans)

我正在寻找一种采用 O(nlogn) 或 O(n) 时间复杂度的优化方法。谢谢。

Answer 1

这在 O(n) 中运行。对于每个字符，检查后面将传输多少个先前的字符。

def get_cost(s):
    result = 0
    seen = [0] * 26
    for c in s:
        idx = ord(c) - ord('a')
        result += 1 + sum(seen[idx+1:])
        seen[idx] += 1
    return result

给定一串桶（字母）。找出将所有水桶带到底部的成本（可能是最小的）

Given a String of Buckets (alphabets). Find the cost (possibly minimal) to bring all the buckets at the base

string

algorithm

hash

data-structures