Piece of Cake

Piece of Cake

Time Limit:1000MS  Memory Limit:65536K
Total Submit:69 Accepted:13

Description

The annual neonatal trials will start next week, at the same time, all old guys of the ACM teams want to reward all M students who work hard in the match. So, we buy N cakes which are of different radius. Consider the height of each cake is 1. 
However, Master Ye consider that every student should assign to the equal size of cake, which means every cake assigned to students should be the same volume. Also, he mentions, one student should assign only one piece of cake. 
Master Ye want you to calculate the maximum volume that every student can get. Can you help him figure out this problem? 

Input

The first line contain the number of test cases,no more than 20. 
The second line contain two integers,1 ≤ N, M ≤ 65536 which means the number of cakes and students 
Then following one line contain N integers represent each cake’s radius,and 1 ≤ r ≤ 65536. 

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 1e−4.

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

Case#1: 28.274
Case#2: 3.272
Case#3: 50.265

题意：给定n个蛋糕的半径以及人数k,现在要求k个人每人只能获得一块蛋糕并且体积相同，问他们最多能得到体积为多少的蛋糕。

题解：因为每个人只能获得一块蛋糕，所以假设他们能得到的体积为V，第i个蛋糕的体积为cake[i]，那么第i个蛋糕可能分成(int)(cake[i]/V)个蛋糕。

我们可以二分体积，然后暴力一遍这个体积能否凑满k块，如果可以，就让V再大点，反之，则让V小一点。

代码：

//************************************************************************//
//*Author : Handsome How                                                 *//
//************************************************************************//
//#pragma comment(linker, "/STA	CK:1024000000,1024000000")
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <ctime>
using namespace std;
typedef long long ll;
const double pi=acos(-1);
//----------------------------------------------------------
ll rr[66666];
int main()
{
	int T,kase=0;
	ll all;
	scanf("%d",&T);
	while(T--){
		all = 0;
		int cake,pep,t;
		scanf("%d %d",&cake,&pep);
		for(int i=1;i<=cake;i++){
			scanf("%d",&t);
			rr[i]=t*t*1ll;
			all+=rr[i];
		}
		double l=0,r = (double)all;
		while(r-l>(1e-5)){
			double mid=(l+r)/2.0;
			int tot = 0,now = cake;
			for(int i = 1;i<=cake;i++)
				tot+=(int)(rr[i]/mid);
			if(tot>=pep)l=mid;
			else r=mid;
		}
		printf("Case#%d: ",++kase);
		printf("%.3lf\n",r*pi);
	}
	return 0;
}