Bob是一名建筑工人，他做数学是为了提高效率。他在一个工地上工作，有n桶水泥，上面标有不同的字符(a–z(。上级严格要求他不能改变水桶的顺序。
在开始他的工作之前，他得到了一个长度为n的字符串s，其中位置为i(1<=i<=n(的字符给了我们第个桶上的标记。他一次只能提一个水桶，然后把它带回基地。在每一轮比赛中，他都有一个标准来决定要拿起哪个水桶。他将取标记有最小字符的桶(a<b<z(，如果有多个桶具有最小字符，那么他将取最靠近底部的一个。取水桶B的费用是他从现场步行到取水桶B时经过的水桶数量(他所取的水桶也包括在内(。在每一轮中，成本都在累积。找出Bob在完成工作时产生的最终成本。
限制
1 < t,m < 10^5
所有测试用例的n之和不超过10^6
样本输入
2
条形码
样本输出
7
解释
- badce-首先，Bob拿下标记为"a"的第二个篮子，并在成本上加2
- bdce-然后他拿下第一个标有"b"的篮筐，并在成本上加1
- dce-然后他拿下第二个有"c"标记的篮筐，并在成本上加2
- 德又一次拿下了第一个有"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(时间复杂性。非常感谢。
这在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