1 条题解

  • 0
    @ 2025-6-16 15:52:30
    #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
    上传者