Pie（经典二分法，变体很多）

题目大意

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

输入的第一行为数据组数T。每组数据的第一行为两个整数N和F （ 1 ≤ N ， F ≤ 10 000 ） ；第二行为 N 个整数 ri（1≤ri≤10 000），即各个派的半径。

思路

• 假设每人分得的披萨面积等效为半径 R的圆
• 每块披萨可以分给几个人呢？ r[i] 表示披萨半径，则是 r[i]^2/R^2 取整个人
• 然后全部累加起来，如果总和大于等于 f+1，则每个人还有分更大的披萨的可能，R取值增大
• 如果总和小于 f+1，则每个人分的太大了，不够分的，R取值减小
• R的取值范围在（0，max（r[i]））
• 一开始先去最大面积的一半作为R，然后小了从（mid，max(r[i])）重复操作，大了从(0,mid)重复操作

#include<iostream>
#include <cmath>
#include <iomanip>

using namespace std;

#define PI acos(-1.0)
#define MIN 1e-11 //设置为double的精度

int pizza_num, people_num;
double rad[10010];

bool judge(double size) {
    int cnt = 0;
    for (int i = 1; i <= pizza_num; i++)
        cnt += (int) (rad[i] * rad[i] / (size * size));
    if (cnt >= people_num)
        return true;
    return false;
}

double bin_search(double l, double r) {
    double mid;
    while (r - l > MIN) {
        mid = r + (l - r) / 2;
        if (judge(mid))  //判断分该半径的pie是否够分
            l = mid;
        else
            r = mid;
    }
    return mid;
}

int main() {
    cin >> pizza_num >> people_num;
    people_num++;
    double r = 0;
    for (int i = 1; i <= pizza_num; i++) {
        cin >> rad[i];
        if (rad[i] > r)
            r = rad[i];
    }
    double ansR = bin_search(0.0, r);
    cout << fixed << setprecision(4) << PI * ansR * ansR << endl;
    return 0;
}

二分与分治：二分可以看作分治的一种特殊情况，分治是将原问题分成子问题分别处理，看似二分只处理了一半，另一半丢弃，但也可以理解为丢弃的过程就是二分合并时的过程。原问题分为两个子问题，子问题再分为两个与原问题性质相同的子问题。当子问题规模小到满足精度要求后，合并。合并过程中因为其他子问题不符合要求，都舍弃，所以合并出来的结果就是计算到最后的那个子问题。

本作品采用《CC 协议》，转载必须注明作者和本文链接