题解：P1081 [NOIP 2012 提高组] 开车旅行

· · 题解

P1081 [NOIP 2012 提高组] 开车旅行

这里提供一种基于 STL set 的预处理到达城市方法。

建议结合其他题解看其他部分的代码和整体思路。

对于这个预处理，不会链表的可以试试这个暴力且容易的思路。

同类练习题，可用 set 或者链表解决：P10466 邻值查找

思路

根据题意，我们预处理到达城市（计算 ga 和 gb 数组）的目标为：对于每个城市 i，找出在它后面的城市中，离它最近或者次近的城市并记录。

因此，我们可以利用 set 的性质：插入集合的元素会自动排序，且支持查找某个元素的位置并利用迭代器获取比它小或者大的元素（通过 ++s.find(x) 等操作就可以）。

考虑如何达成我们的目的：

只需要动态维护一个 set 用来排后面几个城市的高度的序，可以用结构体，顺带记录城市的序号，重载运算符 < 即可。

然后对于每个城市，找出比它高的海拔最低的两个城市，以及比他低的海拔最高的两个城市。容易证明这四个城市之中将会诞生最近和次近的城市。

考虑边界处理问题：

由于迭代器的边界处理不好写，采用生硬的判定如 s.end() 这样的方法需要考虑很多特判情况，太繁琐麻烦了。而且由于我们不仅要判前到顶还要看后是否到顶，且我们需要 ++ 或 -- 两次，因此由于美妙的玄学迭代器方法，非常容易写炸。

解决方案：人为造边界。

实现方法：提前插入两个无限大和无限小的海拔到集合中，将他们作为人为的边界，这样就不用考虑边界问题了。

定义无限大为 0x3f3f3f3f 就可满足本题目要求。

代码

这里采用暴力优先队列维护最小和次小城市。

省略了其余部分。

#define inf 0x3f3f3f3f

struct node //城市信息
{
    int h, id;
};
bool operator < (node a, node b)
{
    return a.h < b.h;
}

struct node2
{
    int dis, high, id;
};
bool operator < (node2 a, node2 b) //优先队列反着写符号
{
    if (a.dis == b.dis) return a.high > b.high;
    return a.dis > b.dis;
}

int n, m;
int H[N], ga[N], gb[N];
set<node> City;

pair<int, int> GetCity(node C[], int h) //获取最近的两个城市信息
{
    int a = 0, b = 0;
    priority_queue<node2> Q;
    for (int i = 1; i <= 4; i++)
    {
        if (C[i].h >= inf || C[i].h <= -inf) continue;
        Q.push({abs(h - C[i].h), C[i].h, C[i].id});
    }
    while (!Q.empty())
    {
        if (!b) b = Q.top().id;
        else
        {
            a = Q.top().id;
            break;
        }
        Q.pop();
    }
    return {a, b};
}

void Init() //初始化ga和gb
{
    City.insert({inf, 0}), City.insert({-inf, 0}), City.insert({inf + 1, 0}), City.insert({- inf - 1, 0});
    for (int i = n, h; i >= 1; i--)
    {
        h = H[i];
        City.insert({h, i});
        node C[5] = {};
        C[1] = *++City.find({h, i});
        C[2] = *--City.find({h, i});
        C[3] = *++++City.find({h, i});
        C[4] = *----City.find({h, i});
        auto res = GetCity(C, h);
        ga[i] = res.first, gb[i] = res.second;
    }
}

signed main()
{
    io.read(n);
    for (int i = 1; i <= n; i++) io.read(H[i]);
    Init();

    //省略其他部分...
    return 0;
}