题解 | #丢手绢#

丢手绢

https://ac.nowcoder.com/acm/problem/207040

算法:双指针

时间复杂度:O(n)
思路:

ii为右端点,jj为左端点;

ii向右走,一开始距离必为i,ji,j之间距离;

ii走到某点时,距离变为i,ji,j之外距离,且ii再向前走只会是距离减小;

所以ii停止,jj开始走,使距离增大,此时距离为i,ji,j之外距离;

jj走到某点时,距离又变为i,ji,j之间距离,ii继续走……

n=int(input())
a=[]
for i in range(n):
    a.append(int(input()))
s=sum(a)
j=0;ans=0;cnt=0
for i in range(n):
    cnt+=a[i]
    while j<=i and s-cnt<cnt:
        ans=max(ans,s-cnt)
        cnt-=a[j]
        j+=1
    ans=max(ans,cnt)
print(ans)
全部评论

相关推荐

06-19 19:06
门头沟学院 Java
码农索隆:别去东软,真学不到东西,真事
点赞 评论 收藏
分享
完美的潜伏者许愿简历...:隐藏信息被你提取出来了,暗示,这就是暗示
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务