关注
O(n*logn)复杂度的 import sys
if __name__ == "__main__":
t,k=sys.stdin.readline().strip().split()
t,k=int(t),int(k)
for _ in range(t):
a,b=sys.stdin.readline().strip().split()
a,b=int(a),int(b)
times=0
count=0
for i in range(a,b+1):
white = 0
times=0
while white<=i:
if white==0:
count+=1
else:
count+=i-white+1
times+=1
white = times * k
print(count)
简化为O(n)的代码:
import sys
if __name__ == "__main__":
t,k=sys.stdin.readline().strip().split()
t,k=int(t),int(k)
for _ in range(t):
a,b=sys.stdin.readline().strip().split()
a,b=int(a),int(b)
count=0
for i in range(a,b+1):
n=i//k
count+=(1+n*i-(1+n)*n*k/2+n)
print(int(count))
测试用例全过了,但是线上通过率0%。说循环有误或者算法复杂度过大。难道要O(1)的复杂度? 求大佬解答
查看原帖
点赞 评论
相关推荐
04-14 14:42
西北大学 产品经理 点赞 评论 收藏
分享

点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 毕业季,给职场新人一些建议 #
25293次浏览 438人参与
# 你的房租占工资的比例是多少? #
22767次浏览 255人参与
# 我的求职总结 #
28586次浏览 477人参与
# 计算机专业还有必要去大厂卷吗 #
20458次浏览 107人参与
# 我的实习日记 #
2442010次浏览 25436人参与
# 薪资一样,你会选择去大厂还是小公司 #
16695次浏览 102人参与
# 辞职之后最想做的一件事 #
11186次浏览 162人参与
# 选offer应该考虑哪些因素 #
19869次浏览 294人参与
# 晒一晒你收到的礼盒 #
62565次浏览 374人参与
# 你怀疑过自己的专业选择吗? #
17577次浏览 201人参与
# 为了秋招你都做了哪些准备? #
11067次浏览 166人参与
# Offer比较,求稳定还是求发展 #
49534次浏览 239人参与
# 你想吐槽公司的哪些规定 #
17685次浏览 68人参与
# 第一份工作应该只看薪资吗 #
138947次浏览 1460人参与
# 非技术岗薪资爆料 #
355757次浏览 2746人参与
# 我的工作日记 #
98323次浏览 1271人参与
# 你见过最离谱的招聘要求是什么? #
188501次浏览 1403人参与
# 你想留在一线还是回老家? #
38279次浏览 449人参与
# 秋招想进国企该如何准备 #
58351次浏览 376人参与
# 工作中的卑微时刻 #
9115次浏览 55人参与