UVA 12097 LA 3635 Pie（二分法）

Pie

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 ≤ 10000: the number of pies and the number of friends.
• One line with N integers r_i with 1 ≤ r_i ≤ 10000: 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

 题目大意：有F+1个人来分N个圆形派，每个人得到的必须是一整块派，而不是几块拼在一起，且面积要相同。求出每个人最多能得到多大面积的派（不必是圆形）

 分析：解决在“最小值最大”的常用方法是二分答案。本题虽然不是这个问题，但仍然可以采用二分答案方法，把问题转化为“是否可以让每人得到一块面积为x的派”。这样的转化相当于多了一个条件，然后求解目标变成了“看看这些条件是否相互矛盾”。
　　会有怎样的矛盾呢？只有一种矛盾，x太大，满足不了所有的F+1个人。这样，我们只需要算一算一共可以切成多少份面积为x的派，然后看看这个数目够不够F+1即可。因为派是不可以拼起来的，所以一个半径为r的派只能切出[PI*r2/x]个派（其他部分就浪费了） ，把所有圆形派能切出的份数加起来即可。

代码如下：

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;

const double PI = acos(-1.0);
const int maxn = 10000 + 5;

int n, f;
double A[maxn];

bool ok(double area) {
  int sum = 0;
  for(int i = 0; i < n; i++) sum += floor(A[i] / area);
  return sum >= f+1;
}

int main() {
  int T;
  scanf("%d", &T);
  while(T--) {
    scanf("%d%d", &n, &f);
    double maxa = -1;
    for(int i = 0; i < n; i++) {
      int r;
      scanf("%d", &r);
      A[i] = PI*r*r; maxa = max(maxa, A[i]);
    }
    double L = 0, R = maxa;
    while(R-L > 1e-5) {
      double M = (L+R)/2;
      if(ok(M)) L = M; else R = M;
    }
    printf("%.5lf
", L);
  }
  return 0;
}