poj1064 Cable master(二分)
Cable master 求电缆的最大长度(二分法)
Description
To buy network cables, the Judging Committee has contacted a local network solutions provider with a request to sell for them a specified number of cables with equal lengths. The Judging Committee wants the cables to be as long as possible to sit contestants as far from each other as possible.
The Cable Master of the company was assigned to the task. He knows the length of each cable in the stock up to a centimeter, and he can cut them with a centimeter precision being told the length of the pieces he must cut. However, this time, the length is not known and the Cable Master is completely puzzled.
You are to help the Cable Master, by writing a program that will determine the maximal possible length of a cable piece that can be cut from the cables in the stock, to get the specified number of pieces.
Input
The input is ended by line containing two 0's.
Output
If it is not possible to cut the requested number of pieces each one being at least one centimeter long, then the output must contain the single number "0.00" (without quotes).
Sample Input
Sample Output
题解
也就是求一个x , l1/ x +l2/x +l3/x +.....=K,求最大的x。求的过程中中间值x ,如果>=k也时 ,要求最大的x.
条件C(x)=可以得到K条长度为x的绳子
区间l=0,r等于无穷大,二分,判断是否符合c(x) C(x)=(floor(Li/x)的总和大于或等于K
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<math.h>
using namespace std;
#define st 1e-8//10^-8
double a[];
int k, n;
int f(double x)
{
int cnt = ;
for (int i = ; i < n; i++)
{
cnt += (int)(a[i] / x); //括号不能少
}
return cnt;
}
int main()
{ double sum;
scanf("%d%d", &n, &k);
sum = ;
for (int i = ; i < n; i++)
{
scanf("%lf", &a[i]);
sum += a[i];
}
sum = sum / k;//平均值一定会比最终取得长度大
double l = , r = sum, mid;
while (fabs(l - r)>st)//控制精度
{
mid = (l + r) / ;
if (f(mid) >= k)//不断逼近,找到可以满足切割数量下的最大长度
l = mid;
else
r = mid;
}
r=r*;
printf("%.2f\n", floor(r)/);//向下取整
}
// 4 2542
// 8.02
// 7.43
// 4.57
// 5.39
// 0.00
最新文章
- parted LVM划分4T磁盘,在线扩展1.5T
- pict(Pairwise Independent Combinatorial Testing)工具使用
- 学习Scala01 环境安装
- [AngularJS] 使用AngularCSS动态加载CSS
- MVC5 + EF6 入门完整教程二
- hdu----(1257)最少拦截系统(dp/LIS)
- PWM控制led渐变
- CONSOLE_SCREEN_BUFFER_INFO 结构体
- git的基本应用(一)
- Object constraint language for code generation from activity models
- ListBox、ListCtrl
- java代码代替xml实现图片
- [JSON_01] JSON 解析
- centos java tomcat 中文乱码解决办法
- EditPlus 4.3.2583 中文版已经发布
- WordPress存在DoS拒绝服务漏洞,推荐删除根目录下的xmlrpc.php
- Sql Server 数据库扩展
- logback的configuration
- echarts事件中获取当前实例
- kubernetes-handbook 阅读笔记