SP1837 PIE - Pie 题解

题目链接

思路

一道简单二分答案题。

对于每个确定的派的体积，设置左边界 \(l\)、右边界 \(r\) 和尝试值 \(mid\)，用 \(\operatorname{check}\) 函数返回在每份有 \(mid\) 那么多派的情况下，可以分成几份。将这些结果加起来，与应分人数进行比较，如果份数小于人数，证明每一份分的太多了，将 \(r\) 的值变为 \(mid\)；反之，则代表可能不是最优解，将 \(l\) 的值变为 \(mid\)。

注意

• 精度问题，使用 cmath 库内的 M_PI 函数 解决。
• 需要分到的人数是朋友数加上我自己，即朋友数加 \(1\)。
• 有多组测试点，每次都应输出结果并换行。

参考代码（请勿抄袭）：

#include<bits/stdc++.h> //包含cmath库 
using namespace std;
int t,n,f,b;//几个问题、派的数量、朋友的数量、派的半径 
double l,r; //二分必备
double v[10010]; //每个派的体积 

int check(double a){//获取每份需要mid那么多，能分成几份 
	int s=0;
	for(int i=1;i<=n;i++){//判断每个派能分给多少个朋友 
		s=s+(int)(v[i]/a);//将答案强转int类型 
	}
	return s;//返回s 
}
int main(){//主函数部分 
	cin>>t;
	while(t--){
		r=0,l=0;//r和l初始化 
		cin>>n>>f;
		f++;//我自己也算 
		for(int i=1;i<=n;i++){
			cin>>b;
			v[i]=M_PI*b*b;//省略了乘1 
			r=max(r,v[i]);//r取最大值 
		}
		r+=0.001;//精度 
		while(r-l>0.0001){//二分，0.0001是卡精度 
			double mid=(l+r)/2;//中间值 
			int k=check(mid);//获取check函数返回的值，用k储存 
			if(k<f){//给的太多了，不够分 
				r=mid;//右边界左移 
			}
			else l=mid;//可能不是最优解，那么左边界右移 
		}
		printf("%.4lf\n",l);//二分结束，直接输出l 
	}
	return 0;
}