网站品质,池州有哪些做网站的,深圳知名网站,国内重大新闻2022题目链接#xff1a;http://poj.org/problem?id3122
题目大意#xff1a;
有 n 块披萨#xff08;大小不一样#xff09;#xff0c; f 个人分#xff0c;包含主人自己 f1 人#xff1b; 每人吃的披萨必须是一块披萨上切下来的。每个人吃的披萨相等#xff0c;披萨可…题目链接http://poj.org/problem?id3122
题目大意
有 n 块披萨大小不一样 f 个人分包含主人自己 f1 人 每人吃的披萨必须是一块披萨上切下来的。每个人吃的披萨相等披萨可以有剩余。求每人吃的最大披萨面积。
思路
假设每人分得的披萨面积等效为半径 R的圆每块披萨可以分给几个人呢 r[i] 表示披萨半径则是 r[i]2/R2 取整个人然后全部累加起来如果总和大于等于 f1则每个人还有分更大的披萨的可能R取值增大如果总和小于 f1则每个人分的太大了不够分的R取值减小R的取值范围在0maxr[i]
Wrong Answer代码
/*** description: 有 n 块披萨大小不一样 f 个人分包含主人自己 f1 人* 每人吃的披萨必须是一块披萨上切下来的。求* 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;elser_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_num1);cout setiosflags(ios::fixed) setprecision(4) PI*r_max_pizza*r_max_pizza endl;delete[] r_pizza;r_pizza NULL;}return 0;
}AC代码主要修改精度问题把求人数的除法改成减法
/*** description: 有 n 块披萨大小不一样 f 个人分包含主人自己 f1 人* 每人吃的披萨必须是一块披萨上切下来的。求* 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_want0){temp - S_we_want; //改成减法不易丢失精度people_get_pizza;}}if(people_get_pizza people)s_low S_we_want;elses_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_pizzapizza_num);s_max_pizza find_max_R(pizza_num,s_pizza,0,s_pizza[pizza_num-1],friend_num1);cout setiosflags(ios::fixed) setprecision(4) PI*s_max_pizza endl;delete[] s_pizza;s_pizza NULL;}return 0;
}
