HRBUST - 1530-程序员宅基地

技术标签: 二分  

题目
My birthday is coming up and traditionally I’m serving 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.
Input
One line with a positive integer: the number of test 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.
Output
For each test case, output one line with the largest 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.
Sample Input
3
3 3
4 3 3
1 24
5
10 5
1 4 2 3 4 5 6 5 4 2
Sample Output
25.1327
3.1416
50.2655

题意:有一个人要给好朋友们分pie吃,每个人分到的pie大小要一样,而且每个人只能有一块,求每个人分到的最大体积。

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const double pi=acos(-1.0);
double s[10010];
int n,f;
int check(double mid)  //判断当前体积是否能保证每个人都能吃到pie
{
	int sum=0;
	for(int i=0;i<n;i++)
	{
		sum+=int(s[i]/mid);  //每块pie按mid分能分成几部分
		if(sum>=f) 
		    return 1;
	}
	return 0;
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		memset(s,0,sizeof(s));  //有多组输入,所以要清空数组
		scanf("%d%d",&n,&f);
		for(int i=0;i<n;i++)
		{
			scanf("%lf",&s[i]);
			s[i]=s[i]*s[i]*pi;  //直接求出每个pie的体积
		}
		f+=1;  //f为朋友的人数,要加上自己
		sort(s,s+n);  //给pie的大小排序
		double l=0,r=s[n-1];  //确定左右边界
		while(r-l>0.00001)  //这是题目中的范围限制
		{
			double mid=(l+r)/2;
			if(check(mid)) l=mid;  //当前体积够分,再次增大
			else r=mid;  //不够,减小
		}
		printf("%.4lf\n",l);
	}
	return 0;
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/w_m_w_m_w_m_w_m/article/details/97681225

智能推荐

天猫商品评论获取_getx5sec-程序员宅基地

文章浏览阅读1.2k次。代码很简单,朋友需要就简单写了一下只针对天猫,其他商品没有测试import requestsimport reimport jsonfrom urllib import parsedef collect_tianmao_goods_comments(goods_url ,cookies): &quot;&quot;&quot;采集天猫商品评论, 没有指定翻页默认第一页。&quot;&quot;&quot; parseRes.._getx5sec

通过secureCRT工具连接Linux系统进行mysql安装全操作图文讲解(上传文件mysql,解压、安装、修改、启动、登录和修改密码和远程连接等)-程序员宅基地

文章浏览阅读928次。虚拟机上解压mysql在我上一篇讲解过了,用到的包也在其中,现在再发一次,需要用的请进行下载:mysql客户端和服务端完整包现在进行安装等以下的操作:(这里安装是建立在上传、解压后的操作,我用的CRT进行以下操作的)1.安装mysql客户端的操作:第一步加载:cd mysql/ (我的mysql文件包是解压在了mysql这个文件夹里面的,这个是新建的,上一篇讲过了)第二步进行操作: rpm -ivh mysql-community-client-5.7.27-1.el7.x86_..._通过securecrt工具连接linux系统进行mysql安装

android viewgroup 事件,android中viewgroup的事件传递分析-程序员宅基地

文章浏览阅读210次。在上一篇中我们分析了从view的dispatchTouchEvent到onTouchListener的onTouch回调到onTouchEvent到onClickLisener的onClickandroid中view事件传递,在后面遗留了两个问题,那就是在onTouchEvent中返回false的时候,只触发到action_down事件,以及在dispatchTouchEvent中返回false也..._android.view.viewgroup public abstract class permissionactivity extends appc

140_单词拆分Ⅱ_单词拆解consequent-程序员宅基地

文章浏览阅读79次。"""给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,在字符串中增加空格来构建一个句子,使得句子中所有的单词都在词典中。返回所有这些可能的句子。说明:分隔时可以重复使用字典中的单词。你可以假设字典中没有重复的单词。示例 1:输入:s = "catsanddog"wordDict = ["cat", "cats", "and", "sand", "dog"]..._单词拆解consequent

【黑马程序员西安中心】为什么这个语言如此火爆?_黑马程序员 大数据-程序员宅基地

文章浏览阅读291次。如今,Python 已经成为一种再主流不过的编程语言了。它天生丽质,易于读写,非常实用,从而赢得了广泛的群众基础,被誉为“宇宙最好的编程语言”,被无数程序员热烈追捧。常言道: “流水的语言,铁打的 Python”,貌似目前它已经“睥睨天下,傲视群雄”了,但你不知道的是,Python 其实并不年轻,它的第一个公开版本发布于1991年,为何这几年 Python 才爆红起来呢?到底它经历了什么?今天,我..._黑马程序员 大数据

随便推点

skywalking agent 8.14.0 源代码解读(二)_keep_tracing-程序员宅基地

文章浏览阅读240次。本章着重介绍链路数据(TraceSegment)是如何从被监控服务端进行采集,整合,输出这一过程,主要涉及到对探针内部启动的服务ContextManager以及链路数据管理的上下文TracingContext的介绍。_keep_tracing

阿里程序员常用的 15 款开发者工具~-程序员宅基地

文章浏览阅读86次。从人工到自动化,从重复到创新,技术演进的历程中,伴随着开发者工具类产品的发展。阿里巴巴将自身在各类业务场景下的技术积淀,通过开源、云上实现或工具等形式对外开放,本文将精选了一些阿里巴巴的开发者工具,希望能帮助开发者们提高开发效率、更优雅的写代码。由于开发者涉及的技术领域众多,笔者仅从自己熟悉的领域,以后端开发者的视角盘点平时可能用得到的工具。每个工具按照以下几点进行介绍:工具名称和简介使用场景使用教程获取方式一、Java 线上诊断工具 ArthasArthas是阿里巴巴 2018 年 9 月开

ObjectARX(VC)-符号表之视口-创建4个等大的视口_objectarx的viewport-程序员宅基地

文章浏览阅读780次。(1)注册一个命令AAAMyGroupCreate4VPorts()(2)获得视口表AcDbViewportTable *pVPortTbl = NULL;acdbHostApplicationServices()-&gt;workingDatabase() -&gt;getViewportTable(pVPortTbl, AcDb::kForWrite);//使用“写”的模式打开数..._objectarx的viewport

python中的常量与变量_pathon的常量-程序员宅基地

文章浏览阅读5.8k次。变量命名由字母、数字、下划线组成,不能以数字开头,并且对字母大小写敏感。所谓的常量就是不能改变的量,比如常用的数学常数 PI 就是一个常量,在python中,通常用全部大写的标识符来表示常量,如:PI=3.1415926但事实上PI仍然是一个变量,python没有任何机制保证PI不会被修改,所以,用全部大写的标识符表示常量只是一个习惯上的用法,实际上,PI的值仍然可以被修改。c++ 中通过..._pathon的常量

一名运维工程师的读书列表_运维工程师书籍-程序员宅基地

文章浏览阅读3.5k次。http://www.baidu-ops.com/2012/08/01/ops-book-list/做应用运维这一行,读了一些书,从好书里面学到了不少知识。希望这个书单不断变长。stackoverflow上面列出了一名程序员都应该学习的书单,这是中文版我把书分为3类:技术, 技术文化, 外延技术文化读本:程序员修炼之道里面的思想不仅适合开发,也适合运_运维工程师书籍

问答机器人三种实现方式_智能问答机器人实现方案有哪些-程序员宅基地

文章浏览阅读1.7k次,点赞2次,收藏5次。一、AIMLAIML,全名为Artificial Intelligence Markup Language(人工智能标记语言),是一种创建自然语言软件代理的XML语言,是由Richard Wallace和世界各地的自由软件社区在1995年至2002年发明的。#语料库<aiml version="1.0.1" encoding="UTF-8"> <category> <pattern>你好</pattern> #用户输入关键字 _智能问答机器人实现方案有哪些