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 ;
}