思路:直接通过斜率优化进行求解。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#define Maxn 1000010
using namespace std;
__int64 sum[Maxn];
__int64 num[Maxn];
int que[Maxn*];
int main()
{
int n,k,head,rear,x;
int i,j;
double ans;
while(scanf("%d%d",&n,&k)!=EOF){
ans=;
for(i=;i<=n;i++){
scanf("%I64d",&num[i]);
sum[i]=sum[i-]+num[i];
}
head=,rear=;
que[++rear]=;
for(i=k;i<=n;i++){
j=i-k+;
while(head<rear&&(sum[i]-sum[que[head+]])*(i-que[head])>=(sum[i]-sum[que[head]])*(i-que[head+]))
head++;
ans=max(ans,(double)((double)sum[i]-(double)sum[que[head]])/(double)((double)i-(double)que[head]));
while(head<rear&&(sum[j]-sum[que[rear]])*(que[rear]-que[rear-])<=(sum[que[rear]]-sum[que[rear-]])*(j-que[rear]))
rear--;
que[++rear]=j;
}
printf("%.2lf\n",ans);
}
return ;
}

最新文章

  1. mysql关于排序值的问题
  2. 20160113第一个ANDRIOD开发日志
  3. SAP学习日志--RFC REMOTE FUNCTION CALL
  4. 3_mysql 主从复制
  5. 制作越狱版本的ipa文件
  6. 初学HTML5系列一:简单介绍
  7. Very Deep Convolutional Networks for Large-Scale Image Recognition
  8. python 自动化接口测试(6)
  9. WPF ListBox 获取listBoxItem
  10. 从零开始学习iftop流量监控(找出服务器耗费流量最多的ip和端口)
  11. es索引管理工具-curator
  12. 全栈开发工程师微信小程序 - 上
  13. [20181105]再论12c set feedback only.txt
  14. python 进程池的简单使用方法
  15. Codeforces510 C. Fox And Names
  16. C# Winfrom 发送邮件验证码&amp;Timer控件
  17. Ubuntu 16.04 源添加
  18. Nginx配置示例
  19. ats显示代理缓存
  20. javaweb经典面试题

热门文章

  1. 【例题收藏】◇例题&#183;V◇ Gap
  2. docker快速安装jenkins
  3. MySQL选择的执行计划性能底下原因分析--实战案例分析
  4. 本地通过VMware Workstation创建虚拟机,配置网络环境
  5. 【c学习-6】
  6. (转)IDE 而言,是 Xcode 的技术比较先进还是 Visual Studio?
  7. tcl之控制流-条件运算、条件测试、逻辑表达
  8. 《算法》第四版 IDEA 运行环境的搭建
  9. 浏览器进程/线程模型及JS运行机制
  10. paramiko基本操作