NOIP2012 Day1 开车旅行

【问题描述】

。。。真心累，不想解释

有n个高度互不相同的城市从左到右在一条直线上分布。两个城市之间的距离恰好为两个城市高度的绝对值。现在小a和小b从某座城市出发，交替开车。小a只会选择从当前位置出发，向右距离第二短的城市，小b只会选择从当前位置出发，向右距离最短的城市，且他们开车的总距离不超过X。

在启程前，小a想知道两个问题：

1.对于一个给定的 X=X_0，从哪一个城市出发，小A 开车行驶的路程总数与小 B行驶的路程总数的比值最小（如果小 B 的行驶路程为 0 ，此时的比值可视为 无穷大，且两个无穷大视为相等）。如果从多个城市出发，小 A 开车行驶的路程总数与小B行驶的路程总数的比值都最小，则输出海拔最高的那个城市。

2.给定x[i],s[i],小A开车总路程和小B开车总路程

【输入样例】

#1

4

2 3 1 4

3

4

1 3

2 3

3 3

4 3

#2

10

4 5 6 1 2 3 7 8 9 10

7

10

1 7

2 7

3 7

4 7

5 7

6 7

7 7

8 7

9 7

10 7

【输出样例】

#1

1

1 1

2 0

0 0

0 0

#2

2

3 2

2 4

2 1

2 4

5 1

5 1

2 1

2 0

0 0

0 0

【数据范围】

100%的数据1≤N,M≤100,000,-10^9≤H≤10^9,0≤X≤10^9，1≤S≤N，0≤Xi≤10^9，保证Hi互不相同

【分析】

一眼看出给定s和x，路线一定是可计算和固定的

首先想到暴力，O(N^2)通过预处理每个点右边的最小值和次小值还可以混个70。（据说当年联赛浙江一等线都只有260.。。）

第一问中枚举每个点和第二问中m个询问使得复杂度变成了O((n+m)*k)

[k为计算一次路线的平均时间]

主要思想是简化预处理。

倍增算法，用A[i][j]表示从i出发交替开车2^j轮，A开过的路程；同理用B[i][j]表示从i出发交替开车2^j轮，B开过的路程；并用f[i][j]表示2^j轮后，到达的目的地。

先将各个城市从低到高排序，再记下每个城市排序后的编号。

把排序后的数列改写成一个双向链表，从原始数列的第一个城市开始枚举，由于他在最左边，则i-2，i-1，i+1,i+2中的两个数即为他的最小和次小点。删去这个节点重复上述步骤。

如此，可以用O(nlogn)的时间完成每个点最小值和次小值的查找（而且主要是排序耗时-.-||）

上面两种优化的结合，可以使在给定x和s情况下，logn的时间求出路程

下面附上代码一份：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=;
const int M=;
long long n,m,x0,large=;
long long h[N];
long long s[N],x[N];
long long min1[N],min2[N];
struct node
{
    long long h,id;
}p[N];
long long af[N],pre[N],nxt[N];
long long f[N][],A[N][],B[N][];
bool cmp(node t,node y)
{
    return t.h<y.h;
}
inline void prepare(int u,int i){//u记得是排序后的位置，i为排序前的位置
    if(pre[u])min1[i]=p[pre[u]].id;
    if((nxt[u]&&p[u].h-p[pre[u]].h>p[nxt[u]].h-p[u].h)||!pre[u])min1[i]=p[nxt[u]].id;
    if(min1[i] == p[pre[u]].id){
        if(pre[pre[u]])min2[i]=p[pre[pre[u]]].id;
        if((nxt[u]&&p[u].h-p[pre[pre[u]]].h>p[nxt[u]].h-p[u].h)||!pre[pre[u]])min2[i]=p[nxt[u]].id;
    }
    else {
        if(pre[u])min2[i]=p[pre[u]].id;
        if((nxt[nxt[u]]&&p[u].h-p[pre[u]].h>p[nxt[nxt[u]]].h-p[u].h)||!pre[u])min2[i]=p[nxt[nxt[u]]].id;
    }
    nxt[pre[u]]=nxt[u];
    pre[nxt[u]]=pre[u];
}
void Init()
{
//  freopen("drive.in","r",stdin);
//  freopen("drive.out","w",stdout);
    scanf("%lld",&n);
    for(int i=;i<=n;i++)
        scanf("%lld",&h[i]);
    scanf("%lld%lld",&x0,&m);
    for(int i=;i<=m;i++)
        scanf("%lld%lld",&s[i],&x[i]);
    for(int i=;i<=n;i++)
    {
        p[i].h=h[i];
        p[i].id=i;
    }
    sort(p+,p+n+,cmp);
    for(int i=;i<=n;i++)
    {
        af[p[i].id]=i;
        pre[i]=i-;
        nxt[i]=i+;
    }
    pre[]=,nxt[n]=;
    memset(min1,,sizeof(min1));
    memset(min2,,sizeof(min2));
    for(int i=;i<=n;i++)
        prepare(af[i],i);
    //before,it's the stage of min1,min2;
    //after,it's the stage of A,B,f;
    for(int i=;i<=n;i++)
    {
        if(min1[i])A[i][]=abs(h[min2[i]]-h[i]);
        if(min2[i])B[i][]=abs(h[min2[i]]-h[min1[min2[i]]]);
        f[i][]=min1[min2[i]];
    }
    while(<<large<=n) large++;
    large--;
    for(int i=;i<=large;i++)
        for(int j=;j<=n;j++)
        {
            f[j][i]=f[f[j][i-]][i-];
            A[j][i]=A[j][i-]+A[f[j][i-]][i-];
            B[j][i]=B[j][i-]+B[f[j][i-]][i-];
        }
    return ;
}
int main()
{
    Init();
    long long ansA(),ansB(),ans=-;
    for(int i=;i<=n;i++)
    {
        long long loc=i,rest=x0;
        long long resa(),resb();
        for(int j=large;j>=;j--)
            if(A[loc][j]+B[loc][j]<=rest&&f[loc][j]!=)
            {
                rest=rest-A[loc][j]-B[loc][j];
                resa+=A[loc][j];
                resb+=B[loc][j];
                loc=f[loc][j];
            }
        if(A[loc][]<=rest&&min2[loc]!=)
        {
            resa+=A[loc][];
            loc=min2[loc];
        }
        if(ans==-)
            ansA=resa,ansB=resb,ans=i;
        else
        {
            if(resb==)
            {
                if(ansB==&&h[ans]<h[i])
                    ansA=resa,ansB=resb,ans=i;
            }
            else
            {
                if(ansB==)
                    ansA=resa,ansB=resb,ans=i;
                else
                {
                    double tmp1,tmp2;
                    tmp1=ansA/(ansB*),tmp2=resa/(resb*);
                    if(tmp2<tmp1||tmp1==tmp2&&h[ans]<h[i])
                        ansA=resa,ansB=resb,ans=i;
                }
            }
        }
    }
    cout<<ans<<endl;
    for(int i=;i<=m;i++)
    {
        long long loc=s[i],rest=x[i];
        long long resa(),resb();
        for(int j=large;j>=;j--)
            if(A[loc][j]+B[loc][j]<=rest&&f[loc][j]!=)
            {
                rest=rest-A[loc][j]-B[loc][j];
                resa+=A[loc][j];
                resb+=B[loc][j];
                loc=f[loc][j];
            }
        if(A[loc][]<=rest&&min2[loc]!=)
        {
            resa+=A[loc][];
            loc=min2[loc];
        }
        printf("%lld %lld\n",resa,resb);
    }
    return ;
}