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

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

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

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

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

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

思路

根据题意，我们预处理到达城市（计算 ga 和 gb 数组）的目标为：对于每个城市

i

，找出在它后面的城市中，离它最近或者次近的城市并记录。

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

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

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

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

考虑边界处理问题：

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

解决方案：人为造边界。

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

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

代码

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

省略了其余部分。

CPP

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

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

文章操作

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

思路

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

考虑边界处理问题：

代码

相关推荐

评论

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