题目链接:http://poj.org/problem?id=3122
题目大意:
有 n 块披萨(大小不一样), f 个人分,包含主人自己 f+1 人;
每人吃的披萨必须是一块披萨上切下来的。每个人吃的披萨相等,披萨可以有剩余。求每人吃的最大披萨面积。
思路:
- 假设每人分得的披萨面积等效为半径 R的圆;
- 每块披萨可以分给几个人呢? r[i] 表示披萨半径,则是 r[i]2/R2 取整个人
- 然后全部累加起来,如果总和大于等于 f+1,则每个人还有分更大的披萨的可能,R取值增大
- 如果总和小于 f+1,则每个人分的太大了,不够分的,R取值减小
- R的取值范围在(0,max(r[i]))
Wrong Answer代码
/**
* @description: 有 n 块披萨(大小不一样), f 个人分,包含主人自己 f+1 人;
* 每人吃的披萨必须是一块披萨上切下来的。求
* @author: michael ming
* @date: 2019/4/20 0:23
* @modified by:
*/
#include <iostream>
#include <iomanip>
#define PI 3.14159265359
using namespace std;
const double error = 1e-7;
double find_max_R(size_t pizza_num, int *r_pizza, double r_low, double r_high, size_t people)
{
double R_we_want = r_low+(r_high-r_low)/2;
size_t people_get_pizza = 0;
while(r_high - r_low > error)
{
people_get_pizza = 0;
R_we_want = r_low+(r_high-r_low)/2;
for(int i = 0; i < pizza_num; ++i)
people_get_pizza += (int)(r_pizza[i]*r_pizza[i]/(R_we_want*R_we_want));
if(people_get_pizza >= people)
r_low = R_we_want;
else
r_high = R_we_want;
}
return R_we_want;
}
int main()
{
size_t t, pizza_num, friend_num;
double r_max_pizza = 0;
cin >> t;
while(t--)
{
cin >> pizza_num >> friend_num;
int *r_pizza = new int [pizza_num];
for(int i = 0; i < pizza_num; ++i)
{
cin >> r_pizza[i];
r_max_pizza = r_pizza[i] > r_max_pizza ? r_pizza[i] : r_max_pizza;
}
r_max_pizza = find_max_R(pizza_num,r_pizza,0,r_max_pizza,friend_num+1);
cout << setiosflags(ios::fixed) << setprecision(4) << PI*r_max_pizza*r_max_pizza << endl;
delete[] r_pizza;
r_pizza = NULL;
}
return 0;
}
复制
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsICMyYTMvw1dvwlMvwlM3VWaWV2Zh1Wa-cmbw5ybzETe65meoFTMvwVN5EDM4kjNtUGall3LcVmdhNXLwRHdo9CXt92YucWbpRWdvx2Yx5yazF2Lc9CX6MHc0RHaiojIsJye.png)
AC代码(主要修改,精度问题,把求人数的除法改成减法)
/**
* @description: 有 n 块披萨(大小不一样), f 个人分,包含主人自己 f+1 人;
* 每人吃的披萨必须是一块披萨上切下来的。求
* @author: michael ming
* @date: 2019/4/20 0:23
* @modified by:
*/
#include <iostream>
#include <iomanip>
#include <math.h>
#include <algorithm>
#define PI acos(-1.0)
using namespace std;
const double error = 1e-7;
double find_max_R(size_t pizza_num, double *s_pizza, double s_low, double s_high, size_t people)
{
double S_we_want = s_low+(s_high-s_low)/2.0;
size_t people_get_pizza = 0;
while(s_high - s_low > error)
{
people_get_pizza = 0;
S_we_want = s_low+(s_high-s_low)/2.0;
for(int i = 0; i < pizza_num; ++i)
{
double temp = s_pizza[i];
while(temp-S_we_want>=0)
{
temp -= S_we_want; //改成减法,不易丢失精度
people_get_pizza++;
}
}
if(people_get_pizza >= people)
s_low = S_we_want;
else
s_high = S_we_want;
}
return S_we_want;
}
int main()
{
size_t t, pizza_num, friend_num;
double s_max_pizza = 0.0;
cin >> t;
while(t--)
{
cin >> pizza_num >> friend_num;
double *s_pizza = new double [pizza_num];
for(int i = 0; i < pizza_num; ++i)
{
cin >> s_pizza[i];
s_pizza[i] *= s_pizza[i];
}
sort(s_pizza, s_pizza+pizza_num);
s_max_pizza = find_max_R(pizza_num,s_pizza,0,s_pizza[pizza_num-1],friend_num+1);
cout << setiosflags(ios::fixed) << setprecision(4) << PI*s_max_pizza << endl;
delete[] s_pizza;
s_pizza = NULL;
}
return 0;
}
复制