POJ3104 Drying [二分]

简介:

题目不是非常难

大体思路:

题意:烘干机,给出一堆衣服的水分a[i],在不加烘干机情况下自己主动每一分钟降低1水分。每分钟能够变改衣服(i)到烘干机中,每分钟降低k水分,求最少须要多少时间。
题解:第一时间就想到使用二分枚据答案+验证这样的思路,只是这题还是有些陷阱须要注意。
1. 验证答案时,假设 a[i] <= mid。让它自然烘干就可以 。 假设a[i] > mid,那么烘干这件衣服能够分成两段时间:使用烘干机时间x1 + 自然烘干时间x2,那么能够列出等式:mid = x1 + x2; a[i] <= kx1+x2;于是得x1 >= (a[i] -mid)/(k-1);即得使用烘干机的最少时间x1
2.注意当k==1时。k-1 == 0。须要特殊处理。直接打出ans = maxV
3.注意当求left+right时,结果可能超出范围,正确的方法应该是left + (right - left)*0.5;



犯了一个非常2的错误,ceil(int/int),应该是ceil(int*1.0/int)

再次验证我的二分写法没错,哇哈哈哈

标准的 

while l<r

l=mid+1;

r=mid;

mid=l+(r-l)/2;

代码例如以下

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;

long long num[111111];
int main()
{
	//cout<<"here"<<endl;
	//cout<<ceil(3.4)<<endl;
	//cout<<ceil(4)<<endl;
	//cout<<"end"<<endl;
	long long n,k;
	long long maxn=0;
	while(scanf("%lld",&n)!=EOF)
	{
			for(long long i=1;i<=n;i++)
			{
				scanf("%lld",&num[i]);
				maxn=max(maxn,num[i]);
			}
			sort(num+1,num+1+n);
			scanf("%lld",&k);
			if(k==1)
			{
				printf("%lld\n",maxn);
				continue;
			}
			long long l=1,r=maxn,mid=(r+l)/2;
			long long ans=0;
			while(l<r)
			{
				//mid=(l+r)/2;
				long long sum=0;
				for(long long i=1;i<=n;i++)
				{
					if(num[i]>mid)
						sum+=ceil((num[i]-mid)*1.0/(k-1));
				}
				if(sum>mid)
					l=mid+1;
				else if(sum<=mid)
				{
					r=mid;
				}
				mid=(l+r)/2;
			}
			printf("%lld\n",mid);
	}
}











本文转自mfrbuaa博客园博客,原文链接:http://www.cnblogs.com/mfrbuaa/p/5116529.html,如需转载请自行联系原作者

相关文章
|
Ubuntu
ubuntu 22.04 阿里源
ubuntu 22.04 阿里源
11748 0
|
前端开发 Java 文件存储
JAVA 文件上传 和 下载
文件上传,也称为upload,是指将本地图片、视频、音频等文件上传到服务器上,可以供其他用户浏览或下载的过程。文件上传在项目中应用非常广泛,我们经常发微博、发微信朋友圈都用到了文件上传功能。
|
消息中间件 存储 Kubernetes
Helm方式部署 zookeeper+kafka 集群 ——2023.05
Helm方式部署 zookeeper+kafka 集群 ——2023.05
1047 0
IntelliJ IDEA 如何实现代码展示自动换行
IntelliJ IDEA 如何实现代码展示自动换行
IntelliJ IDEA 如何实现代码展示自动换行
|
前端开发 机器人 Swift
订阅服务:GitHub 开源库更新提醒
订阅服务:GitHub 开源库更新提醒
1848 0
订阅服务:GitHub 开源库更新提醒
|
7月前
|
机器学习/深度学习 人工智能 图形学
I2V3D:微软+港城大黑科技!单图秒变3D动态视频,相机轨迹自由操控
I2V3D 是由香港城市大学和微软联合开发的图像到视频生成框架,支持将静态图像转换为动态视频,基于3D几何引导实现精确的动画控制,适用于动画制作、视频编辑和内容创作等领域。
171 3
I2V3D:微软+港城大黑科技!单图秒变3D动态视频,相机轨迹自由操控
|
人工智能 算法 物联网
阿里云百炼最新能力升级,你都有哪些期待?
阿里云百炼大模型服务产品全新升级,探索算法和技术创新,共享阿里集团内环业务的模型构建经验。
1480 4
|
Linux C语言
教你在QEMU上运行RISC-V Linux
教你在QEMU上运行RISC-V Linux
|
敏捷开发 开发框架 JavaScript
很牛!Github 上 10 个值得学习的 Springboot 开源项目
很牛!Github 上 10 个值得学习的 Springboot 开源项目
11759 0
|
Web App开发 编解码 移动开发
探秘移动端网页调用摄像头的两种方式
PC 端网页调用摄像头的场景想必大家并不陌生,打开一个网址,开启摄像头开始笔试/视频聊天/直播等。 而在移动端网页调用摄像头的场景你见得多吗?我想答案应该是不多吧(在下见识浅薄)。
1167 0