本文共 2353 字，大约阅读时间需要 7 分钟。

考虑到题目中给出了路径的生成方式，也就是说，从一个固定的点出发，路径是已知的，就可以想到了倍增的思想

计算ga[i]表示i出发次近的点,也就是A开一次车到的地方；

gb[i]表示i之后最近的点,也就是B开一次车到的地方

然后处理f[i,j,k]表示k先出发，从i走j天的到达城市

f[0,j,0]=ga[j], f[0,j,1]=gb[j]i=1 -> f[1,j,k]=f[0,f[0,j,k],1-k]i>1 -> f[i,j,k]=f[i-1,f[i-1,j,k],k]

然后处理一个da[i,j,k]，db[i,j,k]表示k先出发，从j走2^i天后A/B走的距离

具体计算方式和f相似，不再赘述，详见代码

代码

#include
   
    #define rint register int#define MAXN 100010using namespace std;typedef long long ll;int X,S,num[MAXN],m,n,nextA[MAXN],nextB[MAXN],f[MAXN][21],stA[MAXN][21],stB[MAXN][21],ans;ll ansA,ansB;double minn=1e9;const int inf=1e9;struct town{    int h,id,L,R;}a[MAXN];inline ll read(){    register char c=getchar(); register ll x=0; short f=1;    while(c>'9'||c<'0')    {        if(c=='-') f=-1;        c=getchar();    }    while(c>='0'&&c<='9')    {        x=(x<<3)+(x<<1)+c-'0';        c=getchar();    }    return x*f;}inline bool cml(town a,town b){    return a.h
    
     =0;--i)    {        if(f[star][i]&&(ll)(ansA+ansB+stA[star][i]+stB[star][i])<=x)        {            ansA+=stA[star][i];            ansB+=stB[star][i];            star=f[star][i];        }    }    if(nextA[star]&&ansA+ansB+stA[star][0]<=x) ansA+=stA[star][0];    return ;} int main(void){    //freopen("a.in","r",stdin);    n=read();    for(rint i=1;i<=n;++i)    {        a[i].h=read(); a[i].id=i;    }       sort(a+1,a+n+1,cml);    for(rint i=1;i<=n;++i) num[a[i].id]=i;    for(rint i=1;i<=n;++i)    {        a[i].L=i-1; a[i].R=i+1;    }    a[1].L=a[n].R=0;    for(rint i=1;i<=n;++i)    {        int now=num[i],l=a[now].L,r=a[now].R;        if(check(now,l,r))          {            nextB[i]=a[l].id;             nextA[i]=judge(now,a[l].L,r);        }           else                        {            nextB[i]=a[r].id;            nextA[i]=judge(now,l,a[r].R);        }        if(l) a[l].R=r;           if(r) a[r].L=l;    }    for(rint i=1;i<=n;++i)    {        f[i][0]=nextB[nextA[i]];        stA[i][0]=abs(a[num[i]].h - a[num[nextA[i]]].h);        stB[i][0]=abs(a[num[f[i][0]]].h - a[num[nextA[i]]].h);    }     for(rint j=1;j<=19;++j)    {        for(rint i=1;i<=n;++i)        {            f[i][j]=f[f[i][j-1]][j-1];      //倍增             stA[i][j]=stA[i][j-1]+stA[f[i][j-1]][j-1];            stB[i][j]=stB[i][j-1]+stB[f[i][j-1]][j-1];        }    }    X=read();   m=read();    for(rint i=1;i<=n;++i)    {        solve(X,i);        if(ansB&&1.0*ansA/ansB
    
   

转载地址：http://ndwm.baihongyu.com/