博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
POJ2018 Best Cow Fences 二分
阅读量:6484 次
发布时间:2019-06-23

本文共 1500 字,大约阅读时间需要 5 分钟。

实数折磨人啊啊啊啊啊啊啊

好,实数应该是最反人类的东西了......

这个害得我调了0.5天才过。

大意是这样的:给你一个数列,求其中不少于f个的连续数的最大平均值。

不禁想起寒假的课程来...

此处应该二分ans,每次把数列减去ans后判断是否有不少于f的一段sum>=0

大喜过望,写了个二分,然后发现不会O(1)判断...

冥思苦想无果之后不由得去看题解。发现要维护前缀和和1~i-f+1的最小前缀和即可。

然后就被实数卡了一天。。。

最后发现还是写的朴素点好。要相信出题人头脑简单不会拿一大堆if来写二分。

AC代码:

1 #include 
2 #include
3 using namespace std; 4 const int INF = 0x7f7f7f7f, N = 100010; 5 const double eps = 1e-5; 6 int f[N], n, F; 7 double a[N]; 8 bool check(double k) { 9 for(int i=1;i<=n;i++) {10 a[i] = f[i] - k;11 a[i] += a[i-1];12 }13 double small = 0, sum=0; // small != INF, small = 014 for(int i = F; i <= n; i++) {15 sum = a[i] - small;16 if(sum >= 0) {17 return true;18 }19 small = min(small, a[i-F+1]);20 }21 return false;22 }23 24 int main() {25 //freopen("in.in","r",stdin);26 //freopen("my.out","w",stdout);27 scanf("%d%d",&n,&F);28 int large = -INF, small = INF;29 for(int i=1;i<=n;i++) {30 scanf("%d",&f[i]);31 large = max(large, f[i]);32 small = min(small, f[i]);33 }34 double l = small, r = large, mid;35 while(r-l>eps) {36 //printf("%.10lf %.10lf \n",l,r);37 mid = (l + r) / 2;38 if(check(mid)) {39 l = mid;40 }41 else {42 r = mid;43 }44 }45 46 printf("%d",(int)(r*1000));47 return 0;48 }
AC代码在此

 

转载于:https://www.cnblogs.com/huyufeifei/p/8974702.html

你可能感兴趣的文章
解决UILable标点符号居中的问题
查看>>
HTML5新特性教程
查看>>
ImageOptim-无损图片压缩Mac版
查看>>
vue-resumer 项目中 element-ui 遇到的 textarea autosize 问题
查看>>
传统运维团队转型应该注意哪些问题?
查看>>
JavaScript函数(二)
查看>>
Airbnb改进部署管道安全性,规范部署顺序
查看>>
腾讯最大规模裁撤中层干部,让贤年轻人
查看>>
蔡超:入门 Go 语言必须跨越的五个思维误区
查看>>
使用Akka Actor和Java 8构建反应式应用
查看>>
curl常用命令详解
查看>>
saltstack 添加计划任务
查看>>
Puppet module命令参数介绍(六)
查看>>
《UNIX网络编程》中第一个timer_server的例子
查看>>
CISCO 路由器(4)
查看>>
网络服务搭建、配置与管理大全(Linux版)
查看>>
Silverlight 5 Beta新特性[4]文本缩进控制
查看>>
springMVC多数据源使用 跨库跨连接
查看>>
Git服务端和客户端安装笔记
查看>>
Spring Security(14)——权限鉴定基础
查看>>