hdu 1969 Pie(二分查找)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1969
Pie
Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 4513 Accepted Submission(s):
1819
pie. Not just one pie, no, I have a number N of them, of various tastes and of
various sizes. F of my friends are coming to my party and each of them gets a
piece of pie. This should be one piece of one pie, not several small pieces
since that looks messy. This piece can be one whole pie though.
My
friends are very annoying and if one of them gets a bigger piece than the
others, they start complaining. Therefore all of them should get equally sized
(but not necessarily equally shaped) pieces, even if this leads to some pie
getting spoiled (which is better than spoiling the party). Of course, I want a
piece of pie for myself too, and that piece should also be of the same size.
What is the largest possible piece size all of us can get? All the pies
are cylindrical in shape and they all have the same height 1, but the radii of
the pies can be different.
cases. Then for each test case:
---One line with two integers N and F with 1
<= N, F <= 10 000: the number of pies and the number of friends.
---One
line with N integers ri with 1 <= ri <= 10 000: the radii of the
pies.
possible volume V such that me and my friends can all get a pie piece of size V.
The answer should be given as a floating point number with an absolute error of
at most 10^(-3).
#include <iostream>
#include <cstdio>
#include <cmath> using namespace std; #define PI acos(-1.0) int main ()
{
int t;
while (~scanf("%d",&t))
{
while (t--)
{
int n,f,r;
double V[],v=,vmax;
scanf("%d%d",&n,&f);
f=f+;
for (int i=; i<n; i++)
{
scanf("%d",&r);
V[i]=r*r*PI;
v+=V[i];
//cout<<v<<endl;
}
vmax=v/f;
double left,right,mid;
left=;
right=vmax;
int ans;
while ((right-left)>1e-)
{
int flag=,k=;
ans=;
mid=(left+right)/;
for (int i=;i<n;i++)
{
// ans+=(int)(V[i]/mid);
//if (ans>=f)
//flag=1;
double vv=V[i];
while(vv>=mid)
{
vv-=mid;
k++;
//cout<<vv<<" "<<k<<endl;
if(k==f)
{
flag=;
break;
}
}
if(flag==) break;
}
if(flag==)
left=mid;
else
right=mid;
}
printf("%.4lf\n",mid);
}
}
return ;
}
另外一种
#include <iostream>
#include <cstdio>
#include <cmath> using namespace std; #define PI acos(-1.0) int main ()
{
int t;
while (~scanf("%d",&t))
{
while (t--)
{
int n,f,r;
double V[],v=,vmax;
scanf("%d%d",&n,&f);
f=f+;
for (int i=; i<n; i++)
{
scanf("%d",&r);
V[i]=r*r*PI;
v+=V[i];
//cout<<v<<endl;
}
vmax=v/f;
double left,right,mid;
left=;
right=vmax;
int ans;
while ((right-left)>1e-)
{
int flag=,k=;
ans=;
mid=(left+right)/;
for (int i=;i<n;i++)
{
ans+=(int)(V[i]/mid);
if (ans>=f)
flag=;
if(flag==) break;
}
if(flag==)
left=mid;
else
right=mid;
}
printf("%.4lf\n",mid);
}
}
return ;
}
最新文章
- [.net 面向对象程序设计进阶] (26) 团队开发利器(五)分布式版本控制系统Git——图形化Git客户端工具TortoiseGit
- sdk添加新的C文件编译出错
- HDU 5029 Relief grain --树链剖分第一题
- C语言 百炼成钢4
- MongoDB概述&;语法
- UR fall detection dataset
- easyui datagrid 学习
- SQL:每年每月最高的两个温度
- win7 IIS7.0 【IIS 管理器无法验证此内置帐户是否有访问权】
- Javascript经典实例 - 正则表达式
- 开源欣赏wordpress之文章新增页面如何实现。
- SDN基础
- 《Office 365 开发入门指南》公开邀请试读,欢迎反馈
- 解决ssm项目表单数据提交到数据库乱码问题
- day 7-18 mysql case when语句
- 安装GDB-ImageWatch ,在QT中查看图像
- k8s pv 的三种挂载模式
- Linux Shell 编程 教程 常用命令
- eclipse打成可运行jar包,清空运行路径选项
- c++ word类型