POJ3122-Pie-二分答案
2024-10-16 06:50:00
有N个派,F+1个人,每个人分到的体积要相等,而且每个人只能有一块派。
二分答案,对于一个mid,对每个派进行检测,尽量的多分,然后如果份数比F+1大,说明mid可以更大,就把mid给low。注意份数等于F+1时,也要向大的地方靠近。
二分答案的题都是这样的套路。
这种题精度是一个大坑。总是在wa和T之间徘徊。。。前几次wa都是PI写的太短了。
还要注意 double输入用%lf,输出用%f。
#include <cstdio>
#include <algorithm>
#include <cstring> using namespace std; const double esp = 1e-;
const double PI = 3.14159265359; int T,N,F,radii[]; int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&N,&F);
F++;
double low = ,high=,mid; for(int i=;i<N;i++)
{
scanf("%d",&radii[i]);
high = max(high,radii[i]*radii[i]*PI);
} while(high-low>esp)
{
int piece = ;
mid = (low+high)/;
for(int i=;i<N;i++)
{
double v = radii[i]*radii[i]*PI;
int cnt = ;
while((cnt+)*mid < v) cnt++;
piece += cnt;
} //printf("low=%f high=%f piece=%d\n",low,high,piece);
if(piece >= F) low = mid;
else high = mid;
}
printf("%.4f\n",mid);
}
}
最新文章
- Tomcat服务器进击
- JSTL配置
- hibernate-聚合函数分组统计数据查询
- CSS-论css如何纯代码实现内凹圆角
- openswitch db files
- Scala第一章学习笔记
- Javascript基础引用类型之Object
- linux下的开源移动图像监测程序--motion编译与配置
- centos 6.5常见lib库安装
- JavaBean-- DAO设计模式
- string的内存管理问题
- The Singularity is Near---预测人工智能,科技走向的神书---奇点临近
- linux Page cache和buffer cache正解
- opencv的一些功能代码
- 6 week work 1
- python 爬虫-2
- 网易的Airtest
- MySql Delete不走索引问题
- 【Java入门提高篇】Day19 Java容器类详解(二)Map接口
- HDUOJ---1754 Minimum Inversion Number (单点更新之求逆序数)