[NOIP2012 提高组] 开车旅行 -526互联

题目描述

小 $A$ 和小 $B$ 决定利用假期外出旅行，他们将想去的城市从 $1$ 到 $n$ 编号，且编号较小的城市在编号较大的城市的西边，已知各个城市的海拔高度互不相同，记城市 $i$ 的海拔高度为 $h_{i}$ ，城市 $i$ 和城市 $j$ 之间的距离 $d_{i, j}$ 恰好是这两个城市海拔高度之差的绝对值，即 $d_{i, j} = ∣ h_{i} - h_{j} ∣$ 。

旅行过程中，小 $A$ 和小 $B$ 轮流开车，第一天小 $A$ 开车，之后每天轮换一次。他们计划选择一个城市 $s$ 作为起点，一直向东行驶，并且最多行驶 $x$ 公里就结束旅行。

小 $A$ 和小 $B$ 的驾驶风格不同，小 $B$ 总是沿着前进方向选择一个最近的城市作为目的地，而小 $A$ 总是沿着前进方向选择第二近的城市作为目的地（注意：本题中如果当前城市到两个城市的距离相同，则认为离海拔低的那个城市更近）。如果其中任何一人无法按照自己的原则选择目的城市，或者到达目的地会使行驶的总距离超出 $x$ 公里，他们就会结束旅行。

在启程之前，小 $A$ 想知道两个问题：

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

2、对任意给定的 $x = x_{i}$ 和出发城市 $s_{i}$ ，小 $A$ 开车行驶的路程总数以及小 $B$ 行驶的路程总数。

输入格式

第一行包含一个整数 $n$ ，表示城市的数目。

第二行有 $n$ 个整数，每两个整数之间用一个空格隔开，依次表示城市 $1$ 到城市 $n$ 的海拔高度，即 $h_{1}, h_{2} . . . h_{n}$ ，且每个 $h_{i}$ 都是互不相同的。

第三行包含一个整数 $x_{0}$ 。

第四行为一个整数 $m$ ，表示给定 $m$ 组 $s_{i}$ 和 $x_{i}$ 。

接下来的 $m$ 行，每行包含 $2$ 个整数 $s_{i}$ 和 $x_{i}$ ，表示从城市 $s_{i}$ 出发，最多行驶 $x_{i}$ 公里。

输出格式

输出共 $m + 1$ 行。

第一行包含一个整数 $s_{0}$ ，表示对于给定的 $x_{0}$ ，从编号为 $s_{0}$ 的城市出发，小 $A$ 开车行驶的路程总数与小 $B$ 行驶的路程总数的比值最小。

接下来的 $m$ 行，每行包含 $2$ 个整数，之间用一个空格隔开，依次表示在给定的 $s_{i}$ 和 $x_{i}$ 下小 $A$ 行驶的里程总数和小 $B$ 行驶的里程总数。

输入输出样例

输入 #1

输出 #1

输入 #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

输出 #2

说明/提示

【样例1说明】

各个城市的海拔高度以及两个城市间的距离如上图所示。

如果从城市 $1$ 出发，可以到达的城市为 $2, 3, 4$ ，这几个城市与城市 $1$ 的距离分别为 $1, 1, 2$ ，但是由于城市 $3$ 的海拔高度低于城市 $2$ ，所以我们认为城市 $3$ 离城市 $1$ 最近，城市 $2$ 离城市 $1$ 第二近，所以小A会走到城市 $2$ 。到达城市 $2$ 后，前面可以到达的城市为 $3, 4$ ，这两个城市与城市 $2$ 的距离分别为 $2, 1$ ，所以城市 $4$ 离城市 $2$ 最近，因此小B会走到城市 $4$ 。到达城市 $4$ 后，前面已没有可到达的城市，所以旅行结束。

如果从城市 $2$ 出发，可以到达的城市为 $3, 4$ ，这两个城市与城市 $2$ 的距离分别为 $2, 1$ ，由于城市 $3$ 离城市 $2$ 第二近，所以小 $A$ 会走到城市 $3$ 。到达城市 $3$ 后，前面尚未旅行的城市为 $4$ ，所以城市 $4$ 离城市 $3$ 最近，但是如果要到达城市 $4$ ，则总路程为 $2 + 3 = 5 > 3$ ，所以小 $B$ 会直接在城市 $3$ 结束旅行。

如果从城市 $3$ 出发，可以到达的城市为 $4$ ，由于没有离城市 $3$ 第二近的城市，因此旅行还未开始就结束了。

如果从城市 $4$ 出发，没有可以到达的城市，因此旅行还未开始就结束了。

【样例2说明】

当 $x = 7$ 时，如果从城市 $1$ 出发，则路线为 $1 \to 2 \to 3 \to 8 \to 9$ ，小 $A$ 走的距离为 $1 + 2 = 3$ ，小 $B$ 走的距离为 $1 + 1 = 2$ 。（在城市 $1$ 时，距离小 $A$ 最近的城市是 $2$ 和 $6$ ，但是城市 $2$ 的海拔更高，视为与城市 $1$ 第二近的城市，所以小 $A$ 最终选择城市 $2$ ；走到 $9$ 后，小 $A$ 只有城市 $10$ 可以走，没有第二选择可以选，所以没法做出选择，结束旅行）

如果从城市 $2$ 出发，则路线为 $2 \to 6 \to 7$ ，小 $A$ 和小 $B$ 走的距离分别为 $2, 4$ 。

如果从城市 $3$ 出发，则路线为 $3 \to 8 \to 9$ ，小 $A$ 和小 $B$ 走的距离分别为 $2, 1$ 。

如果从城市 $4$ 出发，则路线为 $4 \to 6 \to 7$ ，小 $A$ 和小 $B$ 走的距离分别为 $2, 4$ 。

如果从城市 $5$ 出发，则路线为 $5 \to 7 \to 8$ ，小 $A$ 和小 $B$ 走的距离分别为 $5, 1$ 。

如果从城市 $6$ 出发，则路线为 $6 \to 8 \to 9$ ，小 $A$ 和小 $B$ 走的距离分别为 $5, 1$ 。

如果从城市 $7$ 出发，则路线为 $7 \to 9 \to 10$ ，小 $A$ 和小 $B$ 走的距离分别为 $2, 1$ 。

如果从城市 $8$ 出发，则路线为 $8 \to 10$ ，小 $A$ 和小 $B$ 走的距离分别为 $2, 0$ 。

如果从城市 $9$ 出发，则路线为 $9$ ，小 $A$ 和小 $B$ 走的距离分别为 $0, 0$ （旅行一开始就结束了）。

如果从城市 $10$ 出发，则路线为 $10$ ，小 $A$ 和小 $B$ 走的距离分别为 $0, 0$ 。

从城市 $2$ 或者城市 $4$ 出发小 $A$ 行驶的路程总数与小 $B$ 行驶的路程总数的比值都最小，但是城市 $2$ 的海拔更高，所以输出第一行为 $2$ 。

【数据范围与约定】

对于 $30 %$ 的数据，有 $1 \leq n \leq 20, 1 \leq m \leq 20$ ；
对于 $40 %$ 的数据，有 $1 \leq n \leq 100, 1 \leq m \leq 100$ ；
对于 $50 %$ 的数据，有 $1 \leq n \leq 100, 1 \leq m \leq 1000$ ；
对于 $70 %$ 的数据，有 $1 \leq n \leq 1000, 1 \leq m \leq 1 0^{4}$ ；
对于 $100 %$ 的数据： $1 \leq n, m \leq 1 0^{5}$ ， $- 1 0^{9} \leq h_{i} \leq 1 0^{9}$ ， $1 \leq s_{i} \leq n$ ， $0 \leq x_{i} \leq 1 0^{9}$
数据保证 $h_{i}$ 互不相同。

这个题目给我的感觉不是很好，我读懂后却没有一点头绪。。
（如果是在oi的时候，那我可能就st表或者线段树拿70分跑了，但是现在是acm。。没有骗分）
或者说我一开始的时候根本就没用去往dp的方向想。。好像缺了一个把我引导去想dp的引子
奇怪
好像知道了，这个第二问没有给我dp的感觉，但是这个第一问还是有感觉的
(最近写的题目dp特征都太明显了，突然换类型有点不适应。。）
主要是第一题是一个最优解。。
我知道了，因为第二问没有“我的选择”的体现，而是在询问我一个固定的值，这个其实更像是递推而不是dp，没有搜索不同情况的解的过程
这种类型的dp是要建立不同解之间的关系吗?

倍增。。
像是递推里面用的一个东西吧。。
主要的特征就是，当前的状态既是需要的答案，也是后续答案的一个跳板，那我们就可以不用对每一个i<=n都遍历一遍n，而是倍增的去求，就能够遍历完所有的位置了
（就是我们不需要每一个位置去更新后面所有其他位置的答案，就是这么简单）
我目前的理解就只有这个

对于这题的第一问，我们其实可以发现一个特点，就是其实a开的距离之和起始位置有关，和时间无关，这个的意思就是，我们可以合并两端长度，比如a开到c的长度可以是从a开到b，然后加上从b开到c的长度（虽然不一定）
这个就倍增计算了
这么看的话倍增的特征还是特别明显的，这其实接近一个递推而不是dp
我又想了想，其实应该说的是你第i天和第j天从同一个地点出发，最终的终点肯定是不会变的
所以这应该算是一个递推而不算是一个dp

这个题目。。其实应该先算第二问，第二问出来了第一问也就出来了

我先把做法和代码给搞了，再分析一下该怎么思考和这类题目的特点。
额，学到了一个双向链表求单项最大值次大值位置。。(st表也一样，可能复杂点吧)
我错了，应该是我的写法的问题，双向链表比st表写起来复杂
。。。（这个代码量快赶上我的手写平衡树了。。。。）

这么看的话倍增其实和二分的相似程度很高啊，都有一个类似搜索的过程，然后都是用单调性来快速前进，得到答案
复杂度很相似。。
好吧其实大多数时候不一样

这题我莫名其妙wa了。。只有大数据，调不了，没办法。。
其实感觉没有紫题难度，顶多蓝题
紫题的思维难度和巧妙的地方没有。。代码难度也没有那些状压的紫题难，唯一烦的也就是代码长度了。。我写了6kb，但是写的挺快的，因为没啥麻烦的
可以说是一个非常简单的状压优化dp，很模板
前面套了一个求最小值和次小值，其他没啥了
主要是让我学到了倍增运用的一个特点或者说是范围吧
其他的没啥了

附上我的80分代码。。。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read() {
    char c=getchar();ll a=0,b=1;
    for(;c<'0'||c>'9';c=getchar())if(c=='-')b=-1;
    for(;c>='0'&&c<='9';c=getchar())a=a*10+c-48;return a*b;
}
ll n,dist1[150001],dist2[150001],c[150001],f[17][150001][2],da[17][150001][2],db[17][150001][2];//2^i天，从j出发，k开车（0是a，1是b） 
struct chain
{
    ll next,last,v,id;
    bool con;
}a[150001];
bool mycmp1(chain a,chain b)
{
    return a.v<b.v;
}
bool mycmp2(chain a,chain b)
{
    return a.id<b.id;
}
int main()
{
    freopen("1.in","r",stdin);
    freopen("2.out","w",stdout);
    n=read();
    for(ll i=1;i<=n;i++)
    {
        a[i].v=read();
        a[i].id=i;
    }
    sort(a+1,a+1+n,mycmp1);
    for(ll i=2;i<=n-1;i++)
    {
        a[i].last=a[i-1].id;
        a[i].next=a[i+1].id;
    }
    a[1].last=0;
    a[1].next=a[2].id;
    a[n].last=a[n-1].id;
    a[n].next=0;
    a[0].v=1ll<<60;
    a[n+1].v=1ll<<60;
    sort(a+1,a+1+n,mycmp2);
    for(ll i=1;i<=n;i++)
    {
        ll min1=1ll<<60,min2=1ll<<60,id1=0,id2=0;
        ll j,k,cnt=0;
        for(j=a[i].last,k=a[i].next;;j=a[j].last,k=a[k].next)
        {
            if(min1>abs(a[j].v-a[i].v))
            {
                min2=min1;
                id2=id1;
                min1=abs(a[i].v-a[j].v);
                id1=a[j].id;
            }
            else
            if(min1==abs(a[j].v-a[i].v))
            {
                min2=abs(a[j].v-a[i].v);
                id2=a[j].id;
                if(a[id2].v<a[id1].v)
                {
                    swap(id1,id2);
                    swap(min1,min2);
                }
            }
            else 
            if(min2>abs(a[j].v-a[i].v))
            {
                min2=abs(a[i].v-a[j].v);
                id2=a[j].id;
            }
            else 
            if(min2==abs(a[j].v-a[i].v))
            if(a[j].v<a[id2].v)
            {
                min2=abs(a[i].v-a[j].v);
                id2=a[j].id;
            }
            if(min1>abs(a[k].v-a[i].v))
            {
                min2=min1;
                id2=id1;
                min1=abs(a[i].v-a[k].v);
                id1=a[k].id;
            }
            else
            if(min1==abs(a[k].v-a[i].v))
            {
                min2=abs(a[k].v-a[i].v);
                id2=a[k].id;
                if(a[id2].v<a[id1].v)
                {
                    swap(id1,id2);
                    swap(min1,min2);
                }
            }
            else 
            if(min2>abs(a[k].v-a[i].v))
            {
                min2=abs(a[i].v-a[k].v);
                id2=a[k].id;
            }
            else 
            if(min2==abs(a[k].v-a[i].v))
            if(a[k].v<a[id2].v)
            {
                min2=abs(a[i].v-a[k].v);
                id2=a[k].id;
            }
            if(cnt==1)break;//两次内必出答案 
            cnt=1;
        }
        dist1[i]=id1;
        dist2[i]=id2;
        a[a[i].last].next=a[i].next;
        a[a[i].next].last=a[i].last;
    }//我服了，还是set简单。。 md写个这个东西给我整的汗流浃背。。。 
    
    
    for(ll i=1;i<=n-1;i++)
    {
        f[0][i][0]=dist2[i];
        f[0][i][1]=dist1[i];
        da[0][i][0]=abs(a[i].v-a[dist2[i]].v);
        db[0][i][1]=abs(a[i].v-a[dist1[i]].v);
    }
    f[0][n-1][1]=dist1[n-1];
    f[0][n][0]=f[0][n][1]=0;//边界情况 
    for(ll i=1;i<=double(log(n)/log(2));i++)
    {
        for(ll j=1;j<=n;j++)
        {
            if(i==1)
            {
                f[i][j][0]=f[0][f[i-1][j][0]][1];
                f[i][j][1]=f[0][f[i-1][j][1]][0];
            }
            else
            {
                f[i][j][0]=f[i-1][f[i-1][j][0]][0];
                f[i][j][1]=f[i-1][f[i-1][j][1]][1];//不存在的情况。。
            }
        }
    }
    for(ll i=1;i<=double(log(n)/log(2));i++)
    {
        for(ll j=1;j<=n;j++)
        { 
            if(i==1)
            {
                da[i][j][0]=da[i-1][j][0]+da[i-1][f[i-1][j][0]][1];
                da[i][j][1]=da[i-1][j][1]+da[i-1][f[i-1][j][1]][0];
            }
            else 
            {
                da[i][j][0]=da[i-1][j][0]+da[i-1][f[i-1][j][0]][0];
                da[i][j][1]=da[i-1][j][1]+da[i-1][f[i-1][j][1]][1];
            }
        }
    }
    for(ll i=1;i<=double(log(n)/log(2));i++)
    {
        for(ll j=1;j<=n;j++)
        {
            if(i==1)
            {
                db[i][j][0]=db[i-1][j][0]+db[i-1][f[i-1][j][0]][1];
                db[i][j][1]=db[i-1][j][1]+db[i-1][f[i-1][j][1]][0];
            }
            else 
            {
                db[i][j][0]=db[i-1][j][0]+db[i-1][f[i-1][j][0]][0];
                db[i][j][1]=db[i-1][j][1]+db[i-1][f[i-1][j][1]][1];
            }
        }
    }
    ll x0=read(),m=read(),min1=0,min2=0,id=0;
    ll ned1,ned2;
    for(ll now=1;now<=n;now++)
    {
        ll si=now,xi=x0,ans1=0,ans2=0;
        for(ll i=(log(n)/log(2));i>=0;i--)
        {
            if(i>1)//看看是谁在开车车 
            {
                if(f[i][si][0]!=0&&ans1+ans2+da[i][si][0]+db[i][si][0]<=xi)//没走到了边界 
                {
                    ans1+=da[i][si][0];
                    ans2+=db[i][si][0];
                    si=f[i][si][0];
                }
            }
            else
            {
                if(f[i][si][0]!=0&&ans1+ans2+da[i][si][0]+db[i][si][0]<=xi)
                {
                    ans1+=da[i][si][0];
                    ans2+=db[i][si][0];
                    si=f[i][si][0];
                }
            }
        }
        if(f[0][si][1]!=0&&ans1+ans2+da[0][si][0]+db[0][si][0]<=xi)
        {
            ans2+=db[0][si][1];
            si=f[0][si][1];
        }
        if(ans2!=0&&min2!=0)
        {
            if(double(double(ans1)/double(ans2))<double(double(min1)/double(min2)))
            {
                min1=ans1;
                min2=ans2;
                id=now;
            }
        }
        else
        {
            if(min2==0)
            {
                min1=ans1;
                min2=ans2;
                id=now;
            }
        }
        if(now==30)
        {
            ned1=ans1,ned2=ans2;
        }
    }
    cout<<id<<endl;
//    cout<<min1<<' '<<min2<<' '<<ned1<<' '<<ned2<<endl;
//    double cn1=double(min1)/double(min2),cn2=double(ned1)/double(ned2);
//    cout<<cn1<<' '<<cn2<<endl;
    for(ll T=1;T<=m;T++)
    {
        ll si=read(),xi=read(),ans1=0,ans2=0;
        for(ll i=(double(log(n)/log(2)));i>=0;i--)
        {
            if(i>1)//看看是谁在开车车 
            {
                if(f[i][si][0]!=0&&ans1+ans2+da[i][si][0]+db[i][si][0]<=xi)//没走到了边界 
                {
                    ans1+=da[i][si][0];
                    ans2+=db[i][si][0];
                    si=f[i][si][0];
                }
            }
            else
            {
                if(f[i][si][0]!=0&&ans1+ans2+da[i][si][0]+db[i][si][0]<=xi)
                {
                    ans1+=da[i][si][0];
                    ans2+=db[i][si][0];
                    si=f[i][si][0];
                }
            }
        }
        if(f[0][si][1]!=0&&ans1+ans2+da[0][si][0]+db[0][si][0]<=xi)
        {
            ans2+=db[0][si][1];
            si=f[0][si][1];
        }
        cout<<ans1<<' '<<ans2<<endl;
    }
    return 0;
}
/*
10 
4 5 6 1 2 3 7 8 9 10 
7 
1 
7 7
2 1
*/

然后就要弄其他的倍增了。。
感觉就这题根本没让我认识到倍增优化的难度。。