【kickstart 2021 roundF】第一题 trash bins Python题解

from collections import defaultdict
T=int(input())
for tt in range(T):
    N=int(input())
    ss=input()
    ans=0
    
    ll=[-999999 for nn in range(N)]
    rr=[9999999 for nn in range(N)]
    if ss[0]=='1':
        ll[0]=0
    for nn in range(1,N):
        if ss[nn]=='0':
            ll[nn]=ll[nn-1]
        else:
            ll[nn]=nn
    if ss[N-1]=='1':
        rr[N-1]=N-1
    for nn in range(N-2,-1,-1):
        if ss[nn]=='0':
            rr[nn]=rr[nn+1]
        else:
            rr[nn]=nn
    for nn in range(N):
        ans+=min(nn-ll[nn],rr[nn]-nn)
    print('Case #%d: %d' % (tt+1, ans))