【开车旅行】题解(NOIP2012提高组)

分析

首先我们可以发现，两个询问都可以通过一个子程序来求。

接着，如果每到一个城市再找下一个城市，显然是行不通的。所以首先先预处理从每一个城市开始，小A和小B要去的城市。预处理的方法很多，我用的是双向链表：按高度把城市排序，用双向链表把每个城市的相邻的城市里连起来，再从每个城市按双向链表往两边搜，如果搜到的城市在这个城市的西边就删掉，否则记录。左右分别记录两个城市，排个序就可以的出小A和小B要去的城市了。

然后我们就可以发现这是一棵树，所以倍增。

我们设g[i][j]指从i城市走j^2轮走到的点（一轮指小A和小B各走一次，小A先走），fa[i][j]指指从i城市走j^2轮的小A走过路程，fb[i][j]指指从i城市走j^2轮的小B走过路程。转移显然。

#include <cmath>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
const long long maxlongint=;
using namespace std;
struct lyd
{
    long long last;
    long long next; 
};
lyd a[];
long long h[][],c[][][],qu[][],yh[],lf[],n,m,tot,sum,num,g[][],fa[][],fb[][];
double ans;
void q(long long l,long long r)
{
    long long i=l,j=r,mid=h[(l+r)/][],e;
    while(i<j)
    {
        while(h[i][]<mid) i++;
        while(h[j][]>mid) j--;
        if(i<=j)
        {
            e=h[i][];
            h[i][]=h[j][];
            h[j][]=e;
            e=h[i][];
            h[i][]=h[j][];
            h[j][]=e;
            i++;
            j--;
        }
    }
    if(i<r) q(i,r);
    if(l<j) q(l,j);
}
int work(long long x,long long value)
{
    long long i,j,k=,l;
    for(i=log2(n);i>=;i--)
    {
        if(fa[x][i]+fb[x][i]+k<=value)
        {
            k+=fa[x][i]+fb[x][i];
            lf[]+=fa[x][i];
            lf[]+=fb[x][i];
            x=g[x][i];
        }
    }
    if(c[x][][]+k<=value)
    {
        k+=c[x][][];
        lf[]+=c[x][][];
    }
}
int main()
{
    long long i,j,k,l,x,y;
    scanf("%lld",&n);
    for(i=;i<=n;i++)
    {
        scanf("%lld",&h[i][]);
        yh[i]=h[i][];
        h[i][]=i;
    }
    scanf("%lld",&qu[][]);
    scanf("%lld",&m);
    for(i=;i<=m;i++)
    {
        scanf("%lld%lld",&qu[i][],&qu[i][]);
    }
    q(1,n);
    for(i=;i<=n;i++)
    {
        a[h[i][]].last=h[i-][];
        a[h[i][]].next=h[i+][];
    }
    for(i=;i<=n;i++)
    {
        j=i;
        while(a[j].last!=)
        {
            j=a[j].last;
            if(j<i)
            {
                a[a[j].next].last=a[j].last;
                a[a[j].last].next=a[j].next;
                j=a[j].last;
            }
            if(j!=)
            {
                c[i][][]++;
                c[i][c[i][][]][]=j;
                c[i][c[i][][]][]=abs(yh[i]-yh[j]);
                c[i][c[i][][]][]=yh[j];
                if(c[i][][]==) break;
            }
        }
        j=i;
        while(a[j].next!=)
        {
            j=a[j].next;
            if(j<i)
            {
                a[a[j].next].last=a[j].last;
                a[a[j].last].next=a[j].next;
                j=a[j].next;
            }
            if(j!=)
            {
                c[i][][]++;
                c[i][c[i][][]][]=j;
                c[i][c[i][][]][]=abs(yh[i]-yh[j]);
                c[i][c[i][][]][]=yh[j];
                if(c[i][][]==) break;
            }
        }
        for(j=;j<=c[i][][];j++)
        {
            for(k=;k<=c[i][][];k++)
                if(c[i][j][]<c[i][k][] || c[i][j][]==c[i][k][] && c[i][j][]<c[i][k][])
                {
                    l=c[i][k][];
                    c[i][k][]=c[i][j][];
                    c[i][j][]=l;
                    l=c[i][k][];
                    c[i][k][]=c[i][j][];
                    c[i][j][]=l;
                    l=c[i][k][];
                    c[i][k][]=c[i][j][];
                    c[i][j][]=l;
                }
        }
    }
    for(i=;i<=n;i++)
    {
        g[i][]=c[c[i][][]][][];
        fa[i][]=c[i][][];
        fb[i][]=c[c[i][][]][][];
    }
        for(j=;j<=log2(n);j++)
        {
    for(i=;i<=n;i++)
    {
            g[i][j]=g[g[i][j-]][j-];
            fa[i][j]=fa[i][j-]+fa[g[i][j-]][j-];
            fb[i][j]=fb[i][j-]+fb[g[i][j-]][j-];
        }
    }
    ans=double(maxlongint);
    for(i=;i<=n;i++)
    {
        lf[]=lf[]=;
        work(i,qu[][]);
        if(lf[]!=) 
        if(double(lf[])/double(lf[])<ans) 
        {
            ans=double(lf[])/double(lf[]);
            num=i;
        }
    }
    cout<<num<<endl;
    for(i=;i<=m;i++)
    {
        lf[]=lf[]=;
        work(qu[i][],qu[i][]);
        printf("%lld %lld\n",lf[],lf[]);
    }
}