1 Star 1 Fork 0

bensonrachel/Atcoder_algorithm

加入 Gitee
与超过 1200万 开发者一起发现、参与优秀开源项目,私有仓库也完全免费 :)
免费加入
文件
该仓库未声明开源许可证文件(LICENSE),使用请关注具体项目描述及其代码上游依赖。
克隆/下载
(step4)A. Maximum Average Segment(CF).py 1.69 KB
一键复制 编辑 原始数据 按行查看 历史
# -*- coding: utf-8 -*-
# @project : 《Atcoder》
# @Author : created by bensonrachel on 2021/8/9
# @File : (step4)A. Maximum Average Segment(CF).py
# https://codeforces.com/edu/course/2/lesson/6/4/practice/contest/285069/problem/A
# Given an array of n and a number d. Your task is to find a segment of length at least d, on which the arithmetic mean of the elements is maximum possible.
def check(mid):
global st
global ls
for i in range(1,n+1):
tmp = rate[i]-mid
pre[i] = pre[i-1]+tmp
tmpL = 1
minPre = 0
for i in range(d,n+1):
if(pre[i-d]<minPre):#先找出0到R-D的pre[]的最小值
minPre = pre[i-d]
tmpL = i-d+1#记录最小值的所在位置就是左端点
#这两个if不互斥!独立,所以可能会某次循环两个if都不进去
if(pre[i]>=minPre):#发现存在一个
st = tmpL#start
ls = i#last
return True
return False
def bi():
l = -1
r = 101
for _ in range(100):
mid = (l+r)/2
if(check(mid)):
l = mid#存在有,说明mid还能再大,看图
else:
r = mid
return l
if __name__ == "__main__":
"""
最大化平均值。A. Maximum Average Segment
0,二分平均数,找最大肯定是左二分。
1,推导公式(看黑板照片和理论部分)
2,转化问题(最难一步)
3,在限制条件下找问题的解
4,用到了前缀和。
要保证存在pre[R]>=pre[L]就返回
"""
n,d = map(int,input().split())
rate = [int(i) for i in input().split()]
rate = [0]+rate
pre = [0]*(n+1)
st = 0
ls = 0
x = bi()
print(st,ls)
Loading...
马建仓 AI 助手
尝试更多
代码解读
代码找茬
代码优化
1
https://gitee.com/bensonrachel/atcoder_algorithm.git
git@gitee.com:bensonrachel/atcoder_algorithm.git
bensonrachel
atcoder_algorithm
Atcoder_algorithm
master

搜索帮助