代码拉取完成,页面将自动刷新
# -*- 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)
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。