首页 > 代码库 > 一天一道算法题---6.3---二分运用

一天一道算法题---6.3---二分运用

2024-07-06 23:47:42   226人阅读

感谢微信平台 ： 一天一道算法题 -----  一天多一点进步-----

先来段 废话：

已经 3 4天没更了 主要还是自己 太懒了 。。。。

好 让我们 开始吧

题目链接：

　　　　　　　　　　touch  me 

是不是 有点长啊  最可恶的是 还有张 诱人的 馅饼  ---

　　　　　　　　话说 有个很好的美国系列校园青春 sex movie ---  American Pie  --- 美国派----- 

题目大意：

　　有F+1个人来分N个圆形蛋糕 每个人得到的必是一整块蛋糕 （不是由几块拼在一起的）面积要相同 求每个人最多能得到多大面积的蛋糕 （ 不必是圆形）

tips:

　　这有点类似 你在寻找一个明确范围内寻找一个适合它的最大即最优的解

　　既然我已经指明了 使用 二分思想 那么你只要知道 一个半径为R的蛋糕 只能切出 （ π * r * r )/(S) 这里的S就是你要分给每个人的蛋糕的面积 因为蛋糕不能是由几个蛋糕拼起来的 那么可以确定 可以划分的蛋糕 就是  cnt = ( π*r*r）/（S）的总和  这里的cnt 需要向下取整 就是 如果3.5 就取 3 就这意思

　　好了 负罪感 down

　　贴上我的代码：

　

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cmath>
 4 #include <cstring>
 5 using namespace std;
 6 
 7 int n , m;
 8 const int size = 10010;
 9 const double pi = 3.1415926535898 ;
10 double area[size];
11 
12 bool choose( double s )
13 {
14     int sum = 0;
15     for( int i = 0 ; i<m ; i++ )
16     {
17         sum+=floor(area[i]/s);  //向下取整 3.5->3 人总是整数的 
18     }
19     return sum>=n+1;  //这是个很好的细节 相比你去写 If....else... 简洁 即美
20 }
21 
22 int main()
23 {
24     int t;
25     double l , r , mid , mmax;
26     scanf( "%d",&t );
27     while( t-- )
28     {
29         memset( area , 0 , sizeof(area) );
30         mmax = 0;
31         scanf( "%d %d",&m,&n );//n+1个人 m个蛋糕 一开始 顺序弄错了
32         for( int i = 0 ; i<m ; i++ )
33         {
34             scanf( "%lf",&area[i] );
35             area[i] = area[i]*area[i]*pi;
36             if( area[i]>mmax ) //找出这m块蛋糕的
37                 mmax = area[i];
38         }
39         l = 0;
40         r = mmax;
41         while( r-l>1e-5 )
42         {
43             mid = l + (r-l)/2;
44             if( choose(mid) )
45                 l = mid;
46             else
47                 r = mid;
48         }
49         printf( "%.4lf\n",l );
50     }
51     return 0;
52 }
View Code

 

today:

　　最难得到的两个字叫简单，最难解释的两个字叫幸福，简单即幸福，简单的幸福。

 

 

 

 

 


联系
我们