Löse ABC098-C in Python

Einführung

Die Person von PyBegi hat es gelöst, also werde ich es huckepack nehmen.

** Gedanken ** Aufgrund der Einschränkungen des Problems muss es maximal $ O (N) $ gespeichert werden, sodass es nicht ausreicht, für jeden Anführer zu berechnen. Daher verwenden wir die kumulative Summe. Jetzt können Sie für jeden Leser rechnen, ohne jedes Mal $ summieren zu müssen. Übrigens beträgt der Rechenaufwand für $ sum $ in Python $ O (N) $. Wenn Sie bisher verstanden haben, tun Sie es einfach.

n = int(input())
s = input()

count_e = [0] * n
count_w = [0] * n
for i in range(n):
    if i == 0:
        if s[i] == 'E':
            count_e[i] = 1
        else:
            count_w[i] = 1
        continue
    if s[i] == 'E':
        count_e[i] = count_e[i-1] + 1
        count_w[i] = count_w[i-1]
    else:
        count_e[i] = count_e[i-1]
        count_w[i] = count_w[i-1] + 1

ans = 10 ** 9 #e+w ist höchstens 3*10**Es ist ungefähr 5, aber ich habe einen Spielraum
for i in range(n):
    if s[i] == 'E':
        e = count_e[-1] - count_e[i] #Verwenden Sie die kumulative Summe
        w = count_w[i]
    else:
        e = count_e[-1] - count_e[i] #Verwenden Sie die kumulative Summe
        w = count_w[i] - 1 #Subtrahieren Sie Ihren Anteil
    ans = min(ans,e+w)
print(ans)

Zusammenfassung

Ich bin froh, dass ich einen Algorithmus entwickelt habe, der anhand der Einschränkungen verwendet werden kann. Wir sehen uns wieder, gute Nacht.