派 - 题目列表

题意

把若干圆形派分给所有朋友和自己，每人得到一块面积相同的派，求这块派的最大面积。

思路

半径为 $r$ 的派面积为 $\pi r^2$ 。假设每块面积为 $x$ ，一张派能切出 int(面积 / x) 块；所有派合计至少有 F + 1 块时， $x$ 可行。面积越小可切块数越多，因此可以在 $[0, 最大派面积]$ 上二分。

代码

Python代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20from math import pi

pie_count, friend_count = map(int, input().split())
areas = [pi * radius * radius for radius in map(int, input().split())]
needed_pieces = friend_count + 1


def can_share(area: float) -> bool:
    return sum(int(pie_area / area) for pie_area in areas) >= needed_pieces


low, high = 0.0, max(areas)
for _ in range(100):
    middle = (low + high) / 2
    if can_share(middle):
        low = middle
    else:
        high = middle

print(f"{low:.3f}")

C++代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52/* 
 * 这个题目最坑的是 pi 要定义成 3.141592653589 
 * */
#include <cstdio>

#define pi 3.141592653589
#define JD 0.00001
typedef  long long ll;

ll n,f;
double m[10005];
double _max=0;

void init(){
    scanf("%lld%lld",&n,&f);
    f++;
    int i;
    double t;
    for (i=1;i<=n;i++){
        scanf("%lf",&t);
        m[i] = pi*t*t;
        if( _max < m[i])  _max = m[i];
    }
}

ll check(double  num){
    ll i,cnt = 0;
    for (i=1;i<=n;i++){
        cnt += (m[i] / num);
    }
    return cnt;
}
double first_g(double l,double r){
    double m;
    while( l + JD <  r  ) //表示l和r没有重合
    {
        m = (l+r)/2; // 取中间位置
        ll cnt = check(m);
        if(cnt >= f) //表示 [m+1,r) 满足条件
            l = m+JD;
        else
            r = m;
    }
    return l;
}
int main(){
    init();
    int i,cnt = 0;
    double ans = first_g(0,_max);
    printf("%.3lf\n",ans-JD);
    return 0;
}

复杂度

二分固定 100 次，时间复杂度为 $O(n)$ ，空间复杂度为 $O(n)$ 。

总结

实数二分不必等到端点相等，迭代足够多次即可保证输出精度。

派

目录

题意

思路

代码

Python代码

C++代码

复杂度

总结