YT15-HDU-分pie - c++编程基础

TOP

YT15-HDU-分pie

2015-07-20 17:13:21 来源: 作者: 【大中小】浏览:2次

Problem Description

My birthday is coming up and traditionally I'm serving pie. Not just one pie, no, I have a number N of them, of various tastes and of various sizes. F of my friends are coming to my party and each of them gets a piece of pie. This should be one piece of one pie, not several small pieces since that looks messy. This piece can be one whole pie though.

My friends are very annoying and if one of them gets a bigger piece than the others, they start complaining. Therefore all of them should get equally sized (but not necessarily equally shaped) pieces, even if this leads to some pie getting spoiled (which is better than spoiling the party). Of course, I want a piece of pie for myself too, and that piece should also be of the same size.

What is the largest possible piece size all of us can get? All the pies are cylindrical in shape and they all have the same height 1, but the radii of the pies can be different.

Input

One line with a positive integer: the number of test cases. Then for each test case:
---One line with two integers N and F with 1 <= N, F <= 10 000: the number of pies and the number of friends.
---One line with N integers ri with 1 <= ri <= 10 000: the radii of the pies.

Output

For each test case, output one line with the largest possible volume V such that me and my friends can all get a pie piece of size V. The answer should be given as a floating point number with an absolute error of at most 10^(-3).

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

代码如下：

#include 
  
   
#include 
   
     #include 
    
      #define Pi asin(1.0); //相当于π/2 using namespace std; int main() { int T; int i, n, m, a, sum; double str[10010]; cin>>T; while (T--) { double temp = 0; cin>>n>>m; for ( i = 1; i <= n; i++) { cin>>a; str[i] = a*a * 2 * Pi; //求饼的面积 temp += str[i]; //将所有饼的面积累加 } double low = 0, high = temp / (m + 1); //m+1包括作者自己 double mid; while (high - low > 1e-6) //二分法查找 { sum = 0; mid = (low + high) / 2; for (i = 1 ; i <= n; i++) sum += (int)(str[i] / mid); if (sum >= m + 1) low = mid; else high = mid; } //由于要求所有人一样且不能是两块拼接在一起的，找到那个最合适的平均面积 cout<
      
      
  
      
 运行结果： 
       
        
        
      终于回到学校了，移动的网最近不知道为何进不了CSDN，现在终于进来了，把没发完的一套题继续更新


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：uva 165 Stamps （回溯）	下一篇：Smallest Difference (poj 2718 ..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: