给出一串桶(字母)。找到把所有水桶送到基地的成本(可能是最低的)

Question

鲍勃是一名建筑工人，他做数学来提高效率。他正在一个工地上工作，上面有n桶水泥，上面写着不同的字符(a )。他从上级那里得到严格的命令，他不能改变水桶的顺序。

在开始工作之前，他得到了一个字符串s of length n，其中在i (1 <= i <= n)位置的字符给了我们I‘’th桶上的标记。他一次只能提一个桶，然后把它带回基地。在每一轮比赛中，他都有一个标准去捡桶。他将拿上标有最小字符的水桶(a

约束

1 < t,m < 10^5

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

样本输入

2

巴奇

样本输出

7

解释

• badce --首先，鲍勃拿第二个篮子加上马克'a‘，再加上2英镑。
• bdce--然后他拿第一个带标记'b’的篮子，再加上1英镑。
• dce--然后他拿第二个篮子加上标记'c‘，再加上2个标记。
• de--他再一次拿第一个带标记'd’的篮子，再加上1英镑。

H 126e--再一次把第一个篮子加上标记'e‘，再加上1。h<227/code><>f 228/code>

总成本为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