1 条题解
-
0
#include<stdio.h> // 提供输入输出函数(如scanf/printf) #include<math.h> // 提供数学函数(如acos计算π值) double PI = acos(-1.0); // 计算精确的π值(比直接赋值更准确)通过反余弦函数获取高精度π值,避免手动输入误差 #define eps 1e-5 // 定义浮点精度阈值(但实际代码中未使用) double area[10010]; // 存储所有蛋糕的面积(π*r2)声明全局数组和变量。area数组保存每个蛋糕的面积,m和n分别表示人数和蛋糕数量,便于在函数间共享数据。 int m, n; // m为总人数,n为蛋糕数量 bool check(double mid){ //功能:验证当前假设的每人分得体积mid是否可行。 int sum=0; for(int i=0;i<n;i++) sum+=(int)(area[i]/mid); if(sum>=m)// 判断是否满足需求,sum >= m判断总块数是否足够分配给所有人,若满足则说明mid可能偏小,需尝试更大值 return true; else return false; } int main(){ int T; scanf("%d",&T); while(T--){ scanf("%d%d",&n,&m); // n为蛋糕数量,m为总人数 m++;// 总人数包含主人 double maxx=0; for(int i=0;i<n;i++){ int r; scanf("%d",&r); area[i]=PI*r*r;// 计算每个蛋糕面积 if(maxx<area[i])// 记录最大面积 maxx=area[i]; } //功能:通过二分法确定最大可行体积。 double left = 0, right = maxx; // 初始二分范围,left和right初始化范围为0到最大蛋糕面积。 for (int i = 0; i < 100; i++) { // 固定循环次数确保精度,循环100次:利用固定次数(而非精度终止条件)确保浮点数足够精确(约1e-30精度)。 double mid = left + (right - left) / 2; // 计算中间值,mid = left + (right - left) / 2:避免数值溢出,计算中间值。 if (check(mid)) left = mid; // 可行则增大下界,check(mid)调整边界:若满足条件(块数足够),则尝试更大体积(left=mid);否则缩小范围(right=mid)。 else right = mid; // 不可行则减小上界 } printf("%.4f\n", left); // 输出结果保留四位小数,输出结果:最终left为满足条件的最大体积,保留四位小数。 } return 0; } //poj(3122) //主人过生日,m个人来庆祝,有n块半径不同的圆形蛋糕,有m+1个人分,要求每个人的蛋糕一样重,而且是一整块(每个人的蛋糕都是从一块圆蛋糕切下来的一块)。 //问每个人能分到多大? //输入:第一行输入一个整数表示测试个数。对于每个测试,第一行输入两个整数n,m,分别表示蛋糕的数量和朋友的人数,第二行输入n个整数r表示每个蛋糕的半径 //输出:对于每个测试,输出一行表示答案,取四位小数 //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
- 1
信息
- ID
- 2123
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者