博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
POJ 3104:Drying(二分)
阅读量:7069 次
发布时间:2019-06-28

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

题目大意:你有一台机器可以烘干衣物,现在有n个衣物需要烘干,每件衣服都有一个值表示含水量,烘干机一秒可以烘干k滴水,一件衣服不在烘干机上时会每秒自动蒸发一滴水,求最少用多少时间烘干所有衣服。

分析:

  二分总时间,我们知道,如果一件衣服的含水量不超过总时间,就没有必要用烘干机烘干。对于超过的衣服,我们设它在烘干机上烘的时间为x,自己蒸发的时间为mid-x(mid为二分的时间),如果能烘干衣服,则可得到关系k*x+mid-x>=a[i],得到x>=(a[i]-mid)/(k-1),因为我们希望在能蒸干这件衣服前提下让在烘干机上的时间最短,这样才能使别的衣物有更多时间,所已x取最小值(注意向上取整),我们把所有衣物在烘干机上的最短时间加起来,判断有没有超过mid,然后改变上下界,最终找到答案。

代码:

program drying;var  a:array[0..100000]of int64;  n,i,m:longint; k,l,r,v,s,mid,ans:int64;begin  assign(input,'drying.in');reset(input);assign(output,'drying.out');rewrite(output);  readln(n);  for i:=1 to n do  begin read(a[i]); r:=r+a[i]; if a[i]>m then m:=a[i];end;  readln(k);k:=k-1;  if k=0 then writeln(m)  else  begin  l:=1;  while l<=r do   begin     mid:=(l+r) div 2;s:=0;     for i:=1 to n do       if a[i]>mid then s:=s+ord((a[i]-mid) mod k>0)+(a[i]-mid) div k;     if s<=mid then begin ans:=mid; r:=mid-1; end else l:=mid+1;   end;  writeln(ans);  end;  close(input); close(output);end.
View Code

 

转载于:https://www.cnblogs.com/qtyytq/p/5043261.html

你可能感兴趣的文章
matlab std函数 用法及实例
查看>>
【linux shell系列--1】crontab命令
查看>>
电脑运行 apk
查看>>
PHPExcel读取Excel文件
查看>>
最近写的一个Win8的看漫画程序
查看>>
centos中使用python遇到的几个问题
查看>>
JBOSS在win7环境下启动run.bat无反应
查看>>
redux源码解析
查看>>
我是如何设计 Upload 上传组件的
查看>>
weekly 2019-02-15
查看>>
SpringBoot+jsp项目启动出现404
查看>>
Markdown写作中的图床解决方案(基于七牛云、PicGo)
查看>>
再次简单明了总结flex布局,一看就懂...
查看>>
一步步学会用docker部署应用(nodejs版)
查看>>
无root权限新建git仓库进行多人协同工作
查看>>
【跃迁之路】【687天】程序员高效学习方法论探索系列(实验阶段444-2019.1.6)...
查看>>
假装用某米赛尔号的角度看Python面向对象编程
查看>>
RGBA和OPACITY的区别&DISPLAY和VISIBILITY的区别
查看>>
膨胀的template class成员函数
查看>>
【leetcode】102. Binary Tree Level Order Traversal 水平遍历二叉树
查看>>