题目大意

　　小A和小B决定利用假期外出旅行，他们将想去的城市从1到N编号，且编号较小的城市在编号较大的城市的西边，已知各个城市的海拔高度互不相同，记城市i 的海拔高度为Hi，城市i 和城市j 之间的距离d[i,j]恰好是这两个城市海拔高度之差的绝对值，即d[i,j] = |Hi – Hj|。
　　旅行过程中，小A和小B轮流开车，第一天小A开车，之后每天轮换一次。他们计划选择一个城市S作为起点，一直向东行驶，并且最多行驶X公里就结束旅行。小A和小B的驾驶风格不同，小B总是沿着前进方向选择一个最近的城市作为目的地，而小A总是沿着前进方向选择第二近的城市作为目的地（注意：本题中如果当前城市到两个城市的距离相同，则认为离海拔低的那个城市更近）。如果其中任何一人无法按照自己的原则选择目的城市，或者到达目的地会使行驶的总距离超出X公里，他们就会结束旅行。
　　在启程之前，小A想知道两个问题：
　　1．对于一个给定的X=X0，从哪一个城市出发，小A开车行驶的路程总数与小B行驶的路程总数的比值最小（如果小B的行驶路程为0，此时的比值可视为无穷大，且两个无穷大视为相等）。如果从多个城市出发，小A开车行驶的路程总数与小B行驶的路程总数的比值都最小，则输出海拔最高的那个城市。
　　2. 对任意给定的X=Xi 和出发城市Si，小A开车行驶的路程总数以及小B行驶的路程总数。

题解

如何处理对小A小B一个城市的下一个城市

　　法一：二叉平衡树，key值城市高度。从右往左扫描，见一个城市就往里塞，然后从节点的前驱、后继以及前驱的前驱、后继的后继中选取最小值和次小值。这个可以用set的iterator来实现。

　　法二：双向链表。将所有城市排序接成链表，从左往右扫描，在cur->Prev->Prev, cur->Prev, cur->Next, cur->Next->Next中选取最小值和次小值，然后将其删除。

如何求解

　　树上倍增。将所有城市复制一份，一份表示A开车，一份表示B开车，根据A,B城市之间的转移在两个集合之间连边，出度为0的节点向根节点连边。边权有3个：A行驶距离，B行驶距离（在连接A, B集合的边中，此两个量必然有一个为0），总行驶距离。对这三个权值进行倍增统计，随后各个事情就简单了。

注意事项

　　对于这种题意复杂的题，最好把限制条件写在纸上，不然记着记着就记错了，浪费大把时间。

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <set>

#include <cmath>

#include <vector>

using namespace std;

const int MAX_CITY = 100010, SuperINF = 2147483647;

struct City

{

    int Height, Id;

    bool operator < (const City& a) const

    {

        return Height < a.Height;

    }

}_cities[MAX_CITY];

int TotCity;

struct Graph

{

private:

    static const int MAX_NODE = MAX_CITY * 2 + 50;

    struct Node

    {

        unsigned int Sum[3][20];

        Node *Elder[20];

        vector<Node*> Next;

        int Depth;

    }_nodes[MAX_NODE], *Root;

    int TotNode;

    void Dfs(Node *cur, Node *fa, int depth)

    {

        cur->Depth = depth;

        if (cur != Root)

        {

            for (int i = 1; cur->Elder[i - 1]->Elder[i - 1]; i++)

            {

                cur->Elder[i] = cur->Elder[i - 1]->Elder[i - 1];

                for (int j = 0; j < 3; j++)

                    cur->Sum[j][i] = cur->Sum[j][i - 1] + cur->Elder[i - 1]->Sum[j][i - 1];

            }

        }

        for (int i = 0; i < cur->Next.size(); i++)

            if (cur->Next[i] != fa)

                Dfs(cur->Next[i], cur, depth + 1);

    }

    int Log2(int x)

    {

        int ans = 0;

        while (x >>= 1)

            ans++;

        return ans;

    }

    void Query(Node *cur, int dist, int *ans)

    {

        for (int i = 0; i < 3; i++)

            ans[i] = 0;

        int topFa = Log2(cur->Depth);

        for (int i = topFa; i >= 0; i--)

        {

            if (cur->Elder[i] && cur->Sum[2][i] <= dist)

            {

                for (int j = 0; j < 3; j++)

                    ans[j] += cur->Sum[j][i];

                dist -= cur->Sum[2][i];

                cur = cur->Elder[i];

            }

        }

    }

public:

    void Init(int totNode, int root)

    {

        TotNode = totNode;

        Root = _nodes + root;

    }

    void Build(int u, int v, int w, bool isA)

    {

        Node *cur = _nodes + u, *fa = _nodes + v;

        cur->Elder[0] = fa;

        fa->Next.push_back(cur);

        if (isA)

            cur->Sum[0][0] = cur->Sum[2][0] = w;

        else

            cur->Sum[1][0] = cur->Sum[2][0] = w;

    }

    void GetSum()

    {

        Dfs(Root, NULL, 0);

    }

    void Query(int start, int dist, int *ans)

    {

        return Query(_nodes + start, dist, ans);

    }

}g;

int GetLDelta(set<City>& tree, set<City>::iterator cur)

{

    if (cur == tree.begin())

        return SuperINF;

    set<City>::iterator l = cur;

    l--;

    return abs(cur->Height - l->Height);

}

int GetRDelta(set<City>& tree, set<City>::iterator cur)

{

    set<City>::iterator r = cur;

    r++;

    if (r == tree.end())

        return SuperINF;

    return abs(cur->Height - r->Height);

}

void BuildGraph()

{

    g.Init(TotCity * 2 + 1, TotCity * 2 + 1);

    static set<City> tree;

    for (int i = TotCity; i >= 1; i--)

    {

        tree.insert(_cities[i]);

        set<City>::iterator cur = tree.find(_cities[i]);

        unsigned int lDelta = GetLDelta(tree, cur);

        unsigned int rDelta = GetRDelta(tree, cur);

        if (lDelta < SuperINF || rDelta < SuperINF)

        {

            if (lDelta <= rDelta)

            {

                set<City>::iterator l = cur;

                l--;

                g.Build(cur->Id + TotCity, l->Id, lDelta, false);

                unsigned int llDelta = GetLDelta(tree, l) + lDelta;

                if (llDelta < SuperINF || rDelta < SuperINF)

                {

                    if (llDelta <= rDelta)

                    {

                        l--;

                        g.Build(cur->Id, l->Id + TotCity, llDelta, true);

                    }

                    else

                    {

                        set<City>::iterator r = cur;

                        r++;

                        g.Build(cur->Id, r->Id + TotCity, rDelta, true);

                    }

                }

                else

                    g.Build(cur->Id, TotCity * 2 + 1, SuperINF, true);

            }

            else

            {

                set<City>::iterator r = cur;

                r++;

                g.Build(cur->Id + TotCity, r->Id, rDelta, false);

                unsigned int rrDelta = GetRDelta(tree, r) + rDelta;

                if (lDelta < SuperINF || rrDelta < SuperINF)

                {

                    if (lDelta <= rrDelta)

                    {

                        set<City>::iterator l = cur;

                        l--;

                        g.Build(cur->Id, l->Id + TotCity, lDelta, true);

                    }

                    else

                    {

                        r++;

                        g.Build(cur->Id, r->Id + TotCity, rrDelta, true);

                    }

                }

                else

                    g.Build(cur->Id, TotCity * 2 + 1, SuperINF, true);

            }

        }

        else

        {

            g.Build(cur->Id + TotCity, TotCity * 2 + 1, SuperINF, true);

            g.Build(cur->Id, TotCity * 2 + 1, SuperINF, false);

        }

    }

    g.GetSum();

}

void Read()

{

    scanf("%d", &TotCity);

    for (int i = 1; i <= TotCity; i++)

    {

        scanf("%d", &_cities[i].Height);

        _cities[i].Id = i;

    }

}

void Sol1()

{

    int dist0, ansStart = 0;

    double ansRatio = SuperINF;

    scanf("%d", &dist0);

    int ans[3];

    for (int i = 1; i <= TotCity; i++)

    {

        g.Query(i, dist0, ans);

        double curRatio = (ans[1] == 0 ? SuperINF : 1.0 * ans[0] / ans[1]);

        if (curRatio < ansRatio || (abs(curRatio - ansRatio) < 0.0000001 && _cities[i].Height > _cities[ansStart].Height))

        {

            ansRatio = curRatio;

            ansStart = i;

        }

    }

    printf("%d\n", ansStart);

}

void Sol2()

{

    int qCnt;

    int ans[3];

    scanf("%d", &qCnt);

    while (qCnt--)

    {

        int start, dist;

        scanf("%d%d", &start, &dist);

        g.Query(start, dist, ans);

        printf("%d %d\n", ans[0], ans[1]);

    }

}

int main()

{

    Read();

    BuildGraph();

    Sol1();

    Sol2();

    return 0;

}

巴特西

luogu1081 开车旅行树上倍增

题目大意

题解

如何处理对小A小B一个城市的下一个城市

如何求解

注意事项

最新文章

热门文章

巴特西

luogu1081 开车旅行 树上倍增

题目大意

题解

如何处理对小A小B一个城市的下一个城市

如何求解

注意事项

最新文章

热门文章

luogu1081 开车旅行树上倍增