Bob 是一名建筑工人，他通過數學來提高效率。他正在一個網站上作業，有 n 桶水泥排成一排，上面標有不同的字符 (a - z)。他從前輩那里得到了嚴格的命令，他不能改變桶的順序。
在開始他的作業之前，他得到了一個長度為n的字串s ，其中位置i (1 <= i <= n) 處的字符為我們提供了第 i個桶上的標記。他一次只能提一個桶，帶回基地。在每一輪中，他都有一個關于拿起哪個桶的標準。他會拿走上面標有最小字符的桶（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。
- 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)
I am looking for an optimized approach that takes O(nlogn) or O(n) time complexity. Thank You.
uj5u.com熱心網友回復：
這運行在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
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/435686.html
標籤：string algorithm data-structures hash
上一篇：從字串中取出括號中的文本
下一篇：逐字切串