题解 | qcjj寄快递

N个点，如果直接走，就是dist(a,b)*2秒，或者缩放后走，走的消耗会变低，但缩放后要放大到最大，这2个操作也有自己的耗时，求所有点的最短耗时总和。

容易发现每次都是从最大缩放计算，所以每个点都是独立的。

可以列得耗时函数，其中k是用在缩放屏幕的时间，e是不缩放时候的走路时间（对于单个点来说是个常数），因此这是一个关于k的函数，对k求个导，得到：

然后求极值点，分情况讨论即可

#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;

const double L=log(2.0),T=1.0/L,E=1e-12;

double f(double e){
    if(e<=T+E)return 2*e;
    double x=e*L,k=log(x)/L,p=pow(2,k);
    return 2*k+2*e/p;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int n;cin>>n;
    double x,y,px,py;
    cin>>px>>py;
    double s=0;
    for(int i=1;i<n;++i){
        cin>>x>>y;
        double dx=x-px,dy=y-py;
        double d=sqrt(dx*dx+dy*dy);
        s+=f(d);
        px=x;py=y;
    }
    cout<<fixed<<setprecision(9)<<s<<endl;
    return 0;
}