AtCoder ABC 098 C - Idées d'attention menant à la réponse

problème

C - Attention https://atcoder.jp/contests/abc098/tasks/arc098_a

Pensée menant à la réponse

Le point à noter est que le nombre de personnes qui se retournent lorsque le leader est $ i $ est demandé. En d'autres termes, peu importe le nombre ** que la personne tourne. Il suffit donc d'ajouter le nombre de personnes faisant face à l'ouest de 0 $ à $ i -1 $ et le nombre de personnes faisant face à l'est de $ i + 1 $ à $ N -1 $. Faites ceci pour $ 0 \ leq i \ leq N --1 $ et la valeur minimale sera la réponse.

Pour améliorer l'efficacité du calcul, calculez à l'avance la somme cumulée du nombre de personnes faisant face à l'ouest et du nombre de personnes faisant face à l'est. Le nombre de personnes qui se tournent vers est calculé par $ O (1) $.

répondre

Python.

N = int(input())
S = input()
int_s = [0] * N
cum_sum_w = [0] * (N + 1)
cum_sum_e = [0] * (N + 1)
answers = [0] * N
for i in range(N):
    if (S[i] == 'W'):
        int_s[i] = 1
    else:
        int_s[i] = 0
    cum_sum_w[i + 1] = cum_sum_w[i] + int_s[i]
for i in range(N):
    if (S[i] == 'E'):
        int_s[i] = 1
    else:
        int_s[i] = 0
    cum_sum_e[i + 1] = cum_sum_e[i] + int_s[i]
for i in range(N):
    answers[i] = cum_sum_w[i] + (cum_sum_e[N] - cum_sum_e[i + 1])
print(min(answers))