分治法

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 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!