1 Star 1 Fork 0

bensonrachel/Atcoder_algorithm

加入 Gitee
与超过 1200万 开发者一起发现、参与优秀开源项目,私有仓库也完全免费 :)
免费加入
文件
该仓库未声明开源许可证文件(LICENSE),使用请关注具体项目描述及其代码上游依赖。
克隆/下载
TPM(step2)B. Segment with Big Sum.py 948 Bytes
一键复制 编辑 原始数据 按行查看 历史
# -*- coding: utf-8 -*-
# @project : 《Atcoder》
# @Author : created by bensonrachel on 2021/8/18
# @File : TPM(step2)B. Segment with Big Sum.py
def TPM():
l = 0
sum = 0
res = n + 1
for r in range(n):
sum += rate[r]
while (sum >= s):
res = min(res, r - l + 1)
sum -= rate[l]
l += 1
return res
def TPM_on_theory():#这种写法才可以用来改写做D题
l = 0
sum = 0
res = 1000000
for r in range(n):
sum += rate[r]
while(sum-rate[l] >= s):
sum -= rate[l]
l += 1
if(sum>=s):
res = min(res,r-l+1)
"""
枚举r,维护最大的l,满足sum[l,r]>=s,
然后用r-l+1更新答案即可.
显然l的移动是向右单调的.
"""
if __name__ == "__main__":
n, s = map(int, input().split())
rate = [int(i) for i in input().split()]
x = TPM()
if (x == n + 1):
x = -1
print(x)
Loading...
马建仓 AI 助手
尝试更多
代码解读
代码找茬
代码优化
1
https://gitee.com/bensonrachel/atcoder_algorithm.git
git@gitee.com:bensonrachel/atcoder_algorithm.git
bensonrachel
atcoder_algorithm
Atcoder_algorithm
master

搜索帮助