题解 P1081 【开车旅行】

2018-07-06 20:23:11


主要分为两个部分:预处理和倍增求解

预处理

主要的难题是预处理出当前城市的最近和次近城市,n^2的暴力枚举显然会超时。下面是巧妙的正解:

先按照城市的高度进行排序,不管位置。排序后用双向链表链接各个城市。再按照原来的顺序,也就是按照原来城市的位置顺序进行预处理。排序后,显然,最近和次近一定在i-2,i-1,i+1,i+2中。得出了最近和次近后,就把当前城市删掉,这样后面扫到的所有城市,都不可能出现其他城市在当前城市西边的情况。

倍增

用fa[i][j]表示a从j出发走2^i天行驶的路程,fb[i][j]表示b从j出发走2^i天行驶的路程。然后,一直逼近就行了

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,l,r,j;
struct node
{
    int i, v, l, r;
}d[100005];
int h[100005], p[100005];
int fa[100005][21], fb[100005][21], f[100005][21];
int na[100005],nb[100005],a,b,ans=n;
double minn=1000000000;
bool cmp(node x,node y)
{
    return x.v<y.v;
} 
bool dir()
{
    if(!l) return 0;
    if(!r) return 1;
    return d[j].v-d[l].v<=d[r].v-d[j].v;
}
int pd(int a, int b)
{
    if(!a) return d[b].i;
    if(!b) return d[a].i;
    if(d[j].v-d[a].v<=d[b].v-d[j].v) return d[a].i;
    return d[b].i;
}
void st()
{
    for(int j=1;j<=20;j++)
    {
        for(int i=1;i<=n;i++)
        {
            f[i][j]=f[f[i][j-1]][j-1];
            fa[i][j]=fa[i][j-1]+fa[f[i][j-1]][j-1];
            fb[i][j]=fb[i][j-1]+fb[f[i][j-1]][j-1];
        }
    }
}
void get(long long x, int p)
{
    a=b=0;
    for(int i=20;i>=0;i--)
    {
        if(f[p][i] && (long long)(a+b+fa[p][i]+fb[p][i])<=x)
        {
            a+=fa[p][i];
            b+=fb[p][i];
            p=f[p][i];
        }
    }
    if(na[p] && a+b+fa[p][0]<=x) a+=fa[p][0];
}
int main()
{
    long long x;
    scanf("%d", &n);
    for(int i=1;i<=n;i++) scanf("%d",&d[i].v);
    for(int i=1;i<=n;i++) d[i].i=i;
    sort(d+1,d+n+1,cmp);
    for(int i=1;i<=n;i++) p[d[i].i]=i;
    for(int i=1;i<=n;i++) d[i].l=i-1,d[i].r=i+1;
    d[1].l=d[n].r=0;
    for(int i=1;i<=n;i++)
    {
        j=p[i];l=d[j].l;r=d[j].r;
        if(dir()) nb[i]=d[l].i,na[i]=pd(d[l].l,r);
        else nb[i]=d[r].i,na[i]=pd(l,d[r].r);
        if(l) d[l].r=r;
        if(r) d[r].l=l;
    }
    for(int i=1;i<=n;i++)
    {
        f[i][0]=nb[na[i]];
        fa[i][0]=abs(d[p[i]].v-d[p[na[i]]].v);
        fb[i][0]=abs(d[p[f[i][0]]].v-d[p[na[i]]].v);
    }
    st();
    scanf("%lld%d",&x,&m);
    for(int i=1;i<=n;i++)
    {
        get(x,i);
        if(b && ((double)a)/((double)b)<minn)
        {
            minn=((double)a)/((double)b);
            ans=i;
        }
    }
    printf("%d\n",ans);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%lld",&j,&x);
        get(x,j);
        printf("%d %d\n",a,b);
    }
    return 0;
}