三分法

Posted on | In

二分用于在单调序列上以logn的时间确定某个值，三分则用在凸函数上，即先增后减序列，可以找它的极值。我们需要mid=(l+r)/2和midmid=(mid+r)/2这两个分界点，前者大则令r=midmid，否则令l=mid。

例题：cf939E

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
#include<bits/stdc++.h>
using namespace std;

const int maxn=5e5+1;

double a[maxn];
double sum[maxn];

int p,q;

#define cal(k) (a[p]-(a[p]+sum[k])/(k+1))


int main(){
    cin>>q;
    while(q--){
        int tp;
        cin>>tp;
        if(tp==1){
            double x;
            cin>>x;
            a[++p]=x;
            sum[p]=sum[p-1]+a[p];
        }else{
            int l=1,r=p;	//三分
            while(l<r-1){
                int mid=(l+r)/2;
                int midmid=(mid+r)/2;
                if(cal(mid)<cal(midmid)){
                    l=mid;
                }else{
                    r=midmid;
                }
            }
            double ans=max(cal(l),cal(r));
            printf("%.6f\n",ans);
        }
    }
    return 0;
}