b_bd_罪犯转移(维护滑窗)

题意:求长度为c且满足连续t个元素的和不超过t的子数组的个数

思路:滑动窗口做即可,这是第一版代码(过90%)

感觉没啥问题,但总有一点点别扭,就是

while True:
    try:
        n,t,c=map(int, input().split())
        A=list(map(int, input().split()))
        l=r=s=ans=0
        while r<n:
            if r-l+1==c and s<=t:
                s+=A[r]-A[l]
                l,r,ans=l+1,r+1,ans+1
            else: r,s=r+1,s+A[r]
        print(ans)
    except:
        break

改进思路,最后在加一个额外的判断(因为最后那个r==n-1时,s是继续累加的,而r加完1就出界,没有判断到)

while True:
    try:
        n,t,c=[int(x) for x in input().split(' ')]
        A=list(map(int, input().split()))
        l,r,s,ans=0,c,sum(A[:c]),0
        while r<n:
            if s<=t: ans+=1
            l,r,s=l+1,r+1,s+A[r]-A[l]
        if s<=t: ans+=1
        print(ans)
    except:
        break
原文地址:https://www.cnblogs.com/wdt1/p/14195458.html