【開車旅行】題解(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[]);
    }
}