POJ 3122 二分
2024-09-06 06:47:52
大致题意:
就是公平地分披萨pie
我生日,买了n个pie,找来f个朋友,那么总人数共f+1人
每个pie都是高为1的圆柱体,输入这n个pie的每一个尺寸(半径),如果要公平地把pie分给每一个人(就是所有人得到的pie尺寸一致,但是形状可以不同),而且每个人得到的那份pie必须是从同一个pie上得到的
后面那句很重要,
就是说如果有3个pie, 尺寸分别为1,2,3,
如果要给每人尺寸为2的pie,那么最多分给2个人,而不是3个人
因为第一个pie尺寸为1,小于2,扔掉
第二个pie尺寸为2,等于2,刚好分给一个人
第三个pie尺寸为3,切出尺寸为2的一份,分给一个人,剩下的尺寸为1的就扔掉
千万不要陷入 (1+2+3)/2=3人的误区,这样就变成求平均了
(转自小優YoU的blog http://blog.csdn.net/lyy289065406/article/details/6648565)
就这么随便搞一搞就AC了。
// by SiriusRen
#include <cstdio>
#include <algorithm>
using namespace std;
double pi=3.1415926535898,l,r,a[10005];
int cases,n,f;
int main()
{
scanf("%d",&cases);
while(cases--){
l=r=0;
scanf("%d%d",&n,&f);
for(int i=1;i<=n;i++)scanf("%lf",&a[i]),a[i]*=a[i],r=max(r,a[i]);
while(r-l>=1e-6){
int jy=0;
double mid=(l+r)/2.0;
for(int i=1;i<=n;i++)jy+=(int)a[i]/mid;
if(jy>f)l=mid;
else r=mid;
}
printf("%.4lf\n",r*pi);
}
}
最新文章
- dev LayoutControl布局控件
- Linux sticky bit 目录权限 rwt权限
- js数组合并
- ThinkPHP讲解(八)——显示、修改、添加、删除
- Winform下WebBrowser 编辑模式 监听键盘按键事件
- Matlab画柱状和折线对照图
- linux C(hello world)
- 网上测试了很多关于PYTHON的WEBSOCKET样例,下面这个才成功了
- Lake Counting--poj2386
- MySQL5.6的optimizer_trace
- html5中新增的元素和废除的元素
- python--Numpy and Pandas 基本语法
- ";二分法";-";折半法";-查找算法-之通俗易懂,图文+代码详解-java编程
- Restframe_work 回顾记忆集
- 配置合适的Visual Studio 2017 开发环境(其它版本的也适用)
- Android 应用程序崩溃日志捕捉
- golang 转换markdown文件为html
- BZOJ1258 [CQOI2007]三角形tri 模拟
- ios 回调函数作用
- Centos7 Nginx 开机启动