注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

告别迷茫

梦想与现实的差距,就是我们生活的意义。因为我们有差距,我们才会一直积累,在努力。

 
 
 

日志

 
 

HDU 1969 PIE  

2014-04-29 21:47:46|  分类: 搜索的入门 二分 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |


我的生日快到了,我正在为派传统。不只是一个馅饼,不,我有一个数N,各种口味和各种尺寸的。F的朋友都来参加我的聚会,他们每个人都得到一块馅饼。这应该是一个一个馅饼,而不是几小块因为看起来凌乱。虽然作为一个整体的馅饼

我的朋友是很讨厌的,如果他们其中一个比其他的更大的一块,他们开始抱怨。因此,他们都应该得到同样大小的(但不一定是同样形状)件,即使这会导致一些饼被宠坏了的(这是比破坏党)。当然,我希望我也一块馅饼,那件也应同样大小的。

什么是最大可能的块大小我们都能得到?所有的馅饼的形状是圆柱形的他们都有相同的高1派的半径可以是不同的

输入

一条线与一个正整数:测试用例的数目。然后为每个测试案例

---一行两个整数N和F 1n10F 000馅饼的数量和一些朋友的

---一行n个整数1<RI RI10 000:派的半径

输出

对于每个测试案例输出一行可能的最大体积V我和我的朋友都能得到一个答案的一块馅饼的大小考虑作为一个浮点最多为10 ^绝对误差3


#include<stdio.h>
double chops[10001];
int N,K;
bool chop(double x)/*并不要每一块都要分啊,好难理解,要用二分*/
{
int i,count=0;
for(i=0;i<N;i++)
{
count+=chops[i]/x;
if(count>=K+1) /*可以分为这么多的块啊*/
{
return true;
}
}
return false;
}
double find(double bottom,double top)
{
double mid;
while(top-bottom>=1e-7)
{
mid=(top+bottom)/2;
if(chop(mid))/*有的可以不分也可以啊*/
{
bottom=mid+1e-8; /*如果满足了,那么认为可以继续的分增加分子的大小*/
}
else
{
top=mid-1e-8;
}
}
return (top+bottom)/2;

}
int main()
{
int i;
int t;
double sum;
scanf("%d",&t);
while(t--)
{
sum=0;
scanf("%d%d",&N,&K);
for(i=0;i<N;i++)
{
scanf("%lf",&chops[i]);
chops[i]=chops[i]*chops[i]*3.1415926535897932384626433832795;
sum+=chops[i];
}

printf("%.4lf\n",find(0,sum/(K+1)));
}
}

话说这道题做得我想吐,真的没有想得清楚,分到底是怎么一回事啊,应用二等分。。。。
还可以有的没有用啊 !
不理解啊 啊 啊啊啊啊 啊啊啊 啊啊    
  评论这张
 
阅读(4)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017