Résoudre ABC098-C en Python

introduction

La personne de PyBegi a résolu le problème, je vais donc m'en servir.

** Pensées ** En raison de la limitation du problème, il doit être réglé à environ $ O (N) $ au maximum, il ne suffit donc pas de calculer pour chaque leader. Par conséquent, nous utilisons la somme cumulée. Vous pouvez maintenant calculer pour chaque lecteur sans avoir à $ sum $ à chaque fois. À propos, le montant du calcul pour $ sum $ en Python est $ O (N) $. Si vous comprenez jusqu'ici, faites-le.

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 est au plus 3*10**C'est environ 5, mais j'ai une marge
for i in range(n):
    if s[i] == 'E':
        e = count_e[-1] - count_e[i] #Utiliser la somme cumulée
        w = count_w[i]
    else:
        e = count_e[-1] - count_e[i] #Utiliser la somme cumulée
        w = count_w[i] - 1 #Soustrayez votre part
    ans = min(ans,e+w)
print(ans)

Résumé

Je suis content d'avoir trouvé un algorithme qui peut être utilisé en regardant les contraintes. A bientôt, bonne nuit.