CTU-2017-B 二分_java工程师ctu-程序员宅基地

技术标签: other  

这个题可以直接二分答案来验证这个时间能不能满足题意

验证时要注意一点,后面的多出来的水不能去弥补前面缺少的水

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>

using namespace std;

const int N=100000+3;
double f;
int n;
double c[N];

double J1(double t)
{
    double ans[n+1],pre=0;//pre表示前面多出来的水
    for(int i=1; i<=n; i++) ans[i]=t*f;//初始化t时书龙头出来的水
    for(int i=1; i<=n; i++)
    {
        ans[i]+=pre;
        pre=0;
        if(ans[i]>c[i]) pre=ans[i]-c[i];
    }
    for(int i=1; i<=n; i++)
        if(ans[i]<c[i])
            return false;//如果存在t时有不满的
    return true ;
}

double J2(double t)
{
    double ans[n+1],pre=0;
    for(int i=1; i<=n; i++) ans[i]=t*f;
    for(int i=1; i<=n; i++)
    {
        ans[i]+=pre;
        pre=0;
        if(ans[i]>c[i]) pre=ans[i]-c[i];
    }
    if(ans[n]<c[n]) return false;//二分最后一个满的时间时只需要比较最后是否满
    return true ;
}

int main()
{
    while(scanf("%d%lf",&n,&f)!=EOF)
    {
        for(int i=1; i<=n; i++)
            scanf("%lf",&c[i]);
        double l=0,r=1000000000,mid;
        while(l<r)
        {
            mid=(l+r)/2;
            if(J2(mid)<=0) l=mid+0.0000001;
            else r=mid-0.0000001;
        }
        printf("%.6lf ",mid);
        l=0,r=1000000000;
        while(l<r)
        {
            mid=(l+r)/2;
            if(J1(mid)<=0) l=mid+0.0000001;
            else r=mid-0.0000001;
        }
        printf("%.6lf\n",mid);
    }
    return 0;
}

 

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/alusang/article/details/81951569

智能推荐

【每日一摩斯】-Troubleshooting: High CPU Utilization (164768.1) - 系列3_high cpu utiliaztion-程序员宅基地

文章浏览阅读3.8k次。LGWR & DBWR这两个进程通常是和IO相关的,但是当存在操作系统问题,这两个进程可能"spin(等待)"直到IO操作完成。这种等待是一种CPU操作。异步IO操作的缓慢或失败也能证明它们是高CPU消耗的。如果LGWR间歇地占用100%的CPU资源,那么异步输入输出AIO配置应该重新检查。作为一种临时性的方法,可以设置下面的参数防止LGWR出现等待的现象:_lgwr_async_io_high cpu utiliaztion

word/excel/cad中插入二维码-程序员宅基地

文章浏览阅读1k次。1.有需求为在word文档中插入二维码,寻访度娘后,大部分人推荐使用QRmaker制作。2.找寻QRmaker,网上很多都是1.1版本,后来才知道这个版本有问题(对中文支持不好),偶然得到1.3的版本,用起来很不错,完美中文。下载链接: https://pan.baidu.com/s/1cEYBFK 密码: eubg3.解压,点击控件注册,打开一个word文档,通过控件(度娘控件开启方..._qrmaker放哪里使用

ubantu+win10双系统_windows boot manager可以引导ubantu吗-程序员宅基地

文章浏览阅读249次。我的是双硬盘,固态+500g 的机械硬盘,win10安装在固态里面,现在在机械硬盘里面安装ubantu系统,并且我的固态硬盘分区是efi模式,然后我的机械硬盘的分区是mbr模式;试验了好多次,才勉强成功;主要是分区与引导器的设置,我在机械硬盘里面划分了100g左右的空余空间,设置了swap分区与/挂载点,然后efi选择了以前的window boot manager 所在的efi空间..._windows boot manager可以引导ubantu吗

小白入门ROS-通信编程之<话题通信-2>_ros k自定义消息通信 catkain package-程序员宅基地

文章浏览阅读170次。ROS话题通信自定义话题消息1.在learning_communication功能包目录下,创建msg文件夹。进入msg文件夹,创建Person.msg文件_ros k自定义消息通信 catkain package

hadoop相关整理-程序员宅基地

文章浏览阅读395次。1. 数据结构与算法1.1 书籍(1)算法导论(2)编程之美(3)编程珠玑(4)数据结构(C语言版)(5)CareerCup.Cracking.the.Technical.Interview.Ed4.2010:http://ishare.iask.sina.com.cn/f/12828753.html(6)《程序员面试笔试宝典》,何昊、叶向阳

成功解决:Uncaught TypeError: Cannot read property 'search' of undefined-程序员宅基地

文章浏览阅读9w次,点赞23次,收藏3次。前言今天使用JS进行处理字符串的时候,出现了报错:Uncaught TypeError: Cannot read property 'search' of undefined本来在JS里有search() 这个方法的,但是却一直出现了undefined这个错误,如下图分析原因是出在了字符串身上,没有对字符串是否为空进行判断解决对字符串是否为空进行判断就行啦:i..._uncaught typeerror

随便推点

httpclient post 发送 param 和 body_httpclient.post params、body-程序员宅基地

文章浏览阅读5.3k次,点赞2次,收藏4次。package com.example.demo.webservice;import org.apache.http.client.HttpClient;import org.apache.http.client.methods.CloseableHttpResponse;import org.apache.http.client.methods.HttpPost;import org..._httpclient.post params、body

Java8 list stream collect测试用例小结-程序员宅基地

文章浏览阅读3k次。测试用对象:package com.demo.lee.util;import lombok.AllArgsConstructor;import lombok.Data;@Data@AllArgsConstructorpublic class Student { private Integer id; private String groupId; privat..._list stream collect

目标检测:二维码检测方案_目标检测检测二维码-程序员宅基地

文章浏览阅读7.4k次。Python微信订餐小程序课程视频https://edu.csdn.net/course/detail/36074Python实战量化交易理财系统https://edu.csdn.net/course/detail/35475一、序移动互联网时代,我们的身边,无处不见的二维码,在商店买东西可以用微信或支付宝的付款码、在电影院可以使用二维码在自助取票机上取票,朋友聚会时使用微信二维码互相加好友。移动终端设备的普及,出门只需要携带一步手机,极大方便了人们的日常生活。从技术的角度观察,很多场景下,二维码_目标检测检测二维码

Android Html.fromHtml(String)过时的替代方法_android fromhtml过时-程序员宅基地

文章浏览阅读3.7k次。问题当我们想用TextView来显示一段html代码时,则会用到Html.fromHtml(String)但是现在这个方法是过时的。解决使用API Level 23或之前的设备可以用过时的方法,API Level 24或以上的设备则使用2个参数的方法即可。fromHtml(String source, int flags)即:TextView tv_text = (Text..._android fromhtml过时

前端案例:基于el-table和el-pagination实现数据的分页效果_el-table分页-程序员宅基地

文章浏览阅读9.5w次,点赞60次,收藏79次。基于element-UI实现数据的分页显示效果,数据量较多时和用户管理页常用。_el-table分页

机器学习 - 异常检测 Anomaly Detection(学习笔记)_zhi quan qin anomaly detection acms-程序员宅基地

文章浏览阅读677次。根据输入数据,对不符合预期的模式的数据进行识别,寻找低概率数据(事件)。# train the model (unsupervised study)# 修改概率密度阈值contamination,可调整异常点检测的灵敏度from sklearn.covariance import EllipticEnvelopead_model = EllipticEnvelope(contamination=0.03)ad_model.fit(data)#predict the resulty_p_zhi quan qin anomaly detection acms

推荐文章

热门文章

相关标签