点击打开链接poj 3122
点击打开链接hdu' 1969
思路:二分
分析:
1 题目说的是有n块圆形的饼,饼的高度都是1但是半径不一定相同。现在有f+1个人(算上自己),想要平均分得一块面积相同的饼,必须是一块不能够是组合起来的,问这f+1个人能够分到的最大的面积是多少
2 很明显的二分ans,然后对n块饼进行判断,利用二分逼近的思想求出ans
3 注意这样一题的精度要求很高,pi = 3.1415926535898,还有eps不能取太小会TLE。
代码:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define MAXN 10010
#define pi 3.1415926535898
#define eps 1e-6
int t , N , F;
double sum;
double r[MAXN];
void solve(){
double left , right , mid;
left = 0;
right = 1.0*(pi*sum)/F;
while(right-left > eps){
mid = left+(right-left)/2.0;
int count = 0;
for(int i = 0 ; i < N ; i++){
double s = pi*r[i]*r[i];
int tmp = s/mid;
count += tmp;
}
if(count < F)
right = mid;
else
left = mid;
}
printf("%0.4lf\n" , right);
}
int main(){
scanf("%d" , &t);
while(t--){
scanf("%d%d" , &N , &F);
sum = 0;
F++;
for(int i = 0 ; i < N ; i++){
scanf("%lf" , &r[i]);
sum += r[i]*r[i];
}
solve();
}
return 0;
}
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const double eps = 1e-6;
const double PI = 3.1415926535898;
const int MAXN = 10010;
int n , numFriend;
struct pie{
double r;
double size;
};
pie p[MAXN];
bool judge(double s){
int cnt = 0;
for(int i = 0 ; i < n ; i++)
cnt += p[i].size/s;
return cnt >= numFriend+1 ? true : false;
}
double solve(double Min , double Max){
double left , right , mid;
left = Min , right = Max;
while(right-left > eps){
double mid = left+(right-left)/2;
if(judge(mid))
left = mid;
else
right = mid;
}
return left;
}
int main(){
int Case , pos;
double Min , Max;
scanf("%d" , &Case);
while(Case--){
scanf("%d%d" , &n , &numFriend);
Max = 0.0 , Min = 1>>30;
for(int i = 0 ; i < n ; i++){
scanf("%lf" , &p[i].r);
p[i].size = PI*p[i].r*p[i].r;
Max = max(Max , p[i].size);
Min = min(Min , p[i].size);
}
printf("%.4lf\n" , solve(Min , Max));
}
return 0;
}
分享到:
相关推荐
北大POJ3122-Pie 解题报告+AC代码
看英文题目一开始看不大懂,下面做一下解释:本体就是作者开party然后就做了不同大小不同口味的N个Pie,现在他有k个朋友要参加这个party,但是他的朋友和他要分到相同体积的pie,pie都是圆柱形的,高度全为1....
自动探测POJ、HDU、SOJ、ZOJ水题,对于有志于刷遍各种水题的ACMer来说非常有用
利用vjudge源码改造爬虫抓取vjudge全局共享答案资源。 ACMer,请用于参考思路,对拍代码,不要直接提交。
很多经典的杭电oj与poj习题的ac代码与详解!全部ac,决对没有错误的代码!
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
杭州电子科技大学OJ分类,很适合刚入门的新手哦,分类很详细,是不可多得的资料
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
有题,有解题思路,有解题代码 hdu2516、poj1067和hdu1527、hdu2177、hdu2176等等
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
图论〔Graph Theory〕是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系,用点代表事物,用连接两点的线表示相应两个...
北大POJ1159-Palindrome 解题报告+AC代码
poj分类poj分类poj分类poj分类
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
关于在最小割推荐题目中的源码(包括poj,Hdu两大题库的题目)
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告