https://www.vijos.org/d/SUOI/p/59dc5af7d3d8a1361ae62b97

二分一个答案,然后做一做前缀和,用满足区间大小的最小值减一减,判断答案合不合法

然而还要输出一个最小的区间 太毒瘤了

但其实最后答案中最小区间的端点就只能是刚才做的那个最小值,因为如果不是最小值,那这个答案一定不是最优的

然后再随便对比一下就完事了

(感觉什么都没说清,看代码吧代码好看代码也不好看)

 #include<bits/stdc++.h>
#define pa pair<int,int>
#define ll long long
using namespace std;
const int maxn=1e6+; inline ll rd(){
ll x=;char c=getchar();int neg=;
while(c<''||c>''){if(c=='-') neg=-;c=getchar();}
while(c>=''&&c<='') x=x*+c-'',c=getchar();
return x*neg;
} int N,K,Ma,Mi,num[maxn];
double sum[maxn]; inline bool judge(int &x,int &y,double r){
int a=-,b=N+;
for(int i=;i<=N;i++) sum[i]=sum[i-]+num[i]-r;
double mi=1e9;int mn;bool re=;
for(int i=K;i<=N;i++){
if(mi>=sum[i-K]) mi=sum[i-K],mn=i-K;
if(sum[i]>=mi){
re=;if(b-a>i-mn||(b-a==i-mn&&mn<a)) a=mn,b=i;
}
}if(re) x=a+,y=b;
return re;
} int main(){
int i,j,k;
N=rd();K=rd();Ma=-;Mi=;
for(i=;i<=N;i++) num[i]=rd(),Ma=max(num[i],Ma),Mi=min(num[i],Mi);
double l=Mi-,r=Ma+;int a,b;
while(l<=r-1e-){
double m=(l+r)/;
if(judge(a,b,m)) l=m+1e-;
else r=m-1e-;
}printf("%d %d %.4f",a,b,l);
return ;
}

最新文章

  1. C#设计模式系列:策略模式(Strategy)
  2. github代码上传之命令提交
  3. 3分钟,9个Q&amp;A让你快速知道Docker到底是什么
  4. hdu 1299 Diophantus of Alexandria
  5. 线程NSThread的使用
  6. js常见事件
  7. [读书笔记]算法(Sedgewick著)&#183;第二章.初级排序算法
  8. JQUERY1.9学习笔记 之基本过滤器(二) 等于选择器
  9. Javascript进阶篇——(流程控制语句)笔记整理
  10. 紫薇~还记得大明湖畔的HTML5智力拼图吗?
  11. linux 字符界面浏览器 w3m(转)
  12. Tomcat 7优化
  13. NFS启动时报错Linux NFS:could not open connection for tcp6
  14. SQL Server Profiler追踪数据库死锁
  15. 如何用vue-cli初始化一个vue项目
  16. 015_python原生在线调试工具
  17. SQL Server数据库可能遇到的报错
  18. Openssl编程--源码分析
  19. Java基础-使用Idea进行远程调试
  20. 一个成功的 Git 分支模型

热门文章

  1. Spring Cloud 入门教程(五): Ribbon实现客户端的负载均衡
  2. 基于Nginx+Keepalived的LB服务监控(邮件报警)
  3. linux-阿里云仓库搭建-搭建本地仓库-yum
  4. Individual P1: Preparation
  5. python中的hasattr()、getattr()、setattr()
  6. PHP常用类------生成验证码类Code
  7. 牛客OI周赛7-普及组
  8. Spring Cloud的Zuul的使用问题
  9. Web接口测试-HttpClient
  10. Docker(二十)-Docker容器CPU、memory资源限制