膨胀的木棍

题意

木棍受热后长度增加，但两端仍固定在原位置。把它看成圆弧，求圆弧中点相对原直线的偏移量。

思路

热胀后的弧长为 $S=(1+nC)L$ 。设圆弧半径为 $r$ ，弦长为 $L$ ，圆弧长度是 $2r\arcsin(L/(2r))$ 。半径越大弧长越小，因此二分半径使弧长等于 $S$ ，最后偏移量为 $r-\sqrt{r^2-(L/2)^2}$ 。长度不变时偏移量为零。

代码

Python代码

python

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

length, temperature_change, coefficient = map(float, input().split())
expanded_length = length * (1 + temperature_change * coefficient)

if expanded_length == length:
    print("0.000")
else:
    # 半径越大，对应的圆弧越接近弦，弧长越小。
    low, high = length / 2, 1e18
    for _ in range(200):
        radius = (low + high) / 2
        arc_length = 2 * radius * asin(length / (2 * radius))
        if arc_length > expanded_length:
            low = radius
        else:
            high = radius
    radius = (low + high) / 2
    offset = radius - sqrt(radius * radius - (length / 2) ** 2)
    print(f"{offset:.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
53
54
55
56#include <cstdio>

int l,n,m;
int _min = 0x7f7f7f7f;

int a[50005];
void init(){
    scanf("%d%d%d",&l,&n,&m);
    int i;
    for (i=1;i<=n;i++){
        scanf("%d",&a[i]);
        if( _min > a[i]-a[i-1])
             _min = a[i]-a[i-1];
    }
    if( l - a[n] < _min)
        _min = l - a[n];
    a[n+1] = l;
}

int cnt_remove(int num){
    int i,cnt = 0;
    int pre = 0;
    for(i=1;i<=n;i++){
        if( a[i] - a[pre] < num){
            cnt++;
        }
        else{
            pre = i;
        }
    }
    if( l-a[pre] < num)
        cnt++;
    return cnt;
}

//查找范围是[l,r), a[r] 永远 > key
template <typename T>
int first_g(T a[],int l,int r){
    int mid;
    while( l != r  ) //表示l和r没有重合
    {
        mid = (l+r) >>1; // 取中间位置
        if(cnt_remove(mid) <= m ) //表示 [m+1,r) 满足条件
            l = mid+1;
        else
            r = mid;
    }
    return l;
}

int main(){
    init();
    int ans = first_g(a,_min , l);
    printf("%d\n",ans-1);
    return 0;
}

复杂度

固定进行 200 次二分，时间复杂度和空间复杂度均为 $O(1)$ 。

总结

圆弧模型把“热胀弯曲”转化为单调的几何方程，适合实数二分。

目录

题意

思路

代码

Python代码

C++代码

复杂度

总结