NOIP2012提高组.开车旅行

*前置题目

136. 邻值查找

对于序列中的数$a_i$找到前面和它差最小的一个数输出

#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>

using namespace std;

const int N = 1e5 + 10, INF = 0x3f3f3f3f << 1;

int n;
struct Node {
   
	int x, y;
	bool operator< (const Node &n) const {
   
		return x < n.x;
	}
};
set<Node> s;

int main() {
   
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> n;
	int val;
	cin >> val;
	s.insert({
   val, 1});
	for (int i = 2; i <= n; ++i) {
   
		cin >> val;
		s.insert({
   val, i});
		auto it = s.find({
   val, i});
		Node ans = {
   INF, 0};

		if (++it != s.end()) {
   
			ans = {
   (*it).x - val, (*it).y};
		}
		it--;
		if (it != s.begin()) {
   
			it--;
			if (val - (*it).x <= ans.x) {
   
				ans = {
   val - (*it).x, (*it).y};
			}
		}

		cout << ans.x << " " << ans.y << "\n";
	}

	return 0;
}

题目

293. 开车旅行

算法标签: 倍增优化, $set$

思路

不难发现, 小$A$或者小$B$从起始位置从一个位置出发, 走到的终点是确定的, 因此可以预处理小$A$出发和小$B$出发能走到的位置, 对于题目的第一个询问, 扫描一遍所有位置, 计算比值, 对于第二个询问直接模拟会超时, 因此需要优化

考虑倍增优化, 首先预处理出小$A$和小$B$从每个城市走最终能到达的城市$f[0][i][j]$和$f[1][i][j]$, $0$代表小$A$, $1$代表小$B$, 从城市$i$出发, 走$2^j$步到达的城市

还要预处理走过的距离, 分为$da$数组和$db$数组, 有下面四个情况, $da[0][i][j],da[1][i][j],db[0][i][j],db[1][i][j]$, 前两项代表$A$走过的距离, 后两项代表$B$走过的距离, 这样就可以迅速的计算出询问$2$

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<LL, int> PLI;
const int N = 100010, M = 17;
const LL INF = 1e18;

int n, h[N];
int ga[N], gb[N];
int f[2][N][M];
LL da[2][N][M];
LL db[2][N][M];

void init_g() {
   
	set<PLI> s;
	s.insert({
   INF, 0}), s.insert({
   INF + 1, 0});
	s.insert({
   -INF, 0}), s.insert({
   -INF - 1, 0});

	PLI cand[4];
	for (int i = n; i >= 1; i--) {
   
		PLI t(h[i], i);
		auto j = s.upper_bound(t);
		j++;

		for (int k = 0; k < 4; k++) {
   
			cand[k] = *j;
			j--;
		}

		LL d1 = INF, d2 = INF;
		int p1 = 0, p2 = 0;
		for (int k = 3; k >= 0; k--) {
   
			LL d = abs(h[i] - cand[k].x);
			if (d < d1) {
   
				d2 = d1, d1 = d;
				p2 = p1, p1 = cand[k].y;
			}
			else if (d < d2) {
   
				d2 = d;
				p2 = cand[k].y;
			}
		}
		ga[i] = p2, gb[i] = p1;
		s.insert(t);
	}
}

void init_f() {
   
	// 初始化第0阶
	for (int i = 1; i <= n; i++) {
   
		f[0][i][0] = ga[i];
		f[1][i][0] = gb[i];
	}

	for (int j = 1; j < M; j++) {
   
		for (int i = 1; i <= n; i++) {
   
			for (int k = 0; k < 2; k++) {
   
				if (j == 1) {
   
					f[k][i][j] = f[1 - k][f[k][i][0]][0];
				}
				else {
   
					f[k][i][j] = f[k][f[k][i][j - 1]][j - 1];
				}
			}
		}
	}
}

// 计算两个城市之间的距离
int get_dist(int a, int b) {
   
	return abs(h[a] - h[b]);
}

// 初始化距离数组da和db
void init_d() {
   
	// 初始化第0阶距离
	for (int i = 1; i <= n; i++) {
   
		da[0][i][0] = get_dist(i, ga[i]);
		db[1][i][0] = get_dist(i, gb[i]);
	}

	// 计算更高阶的距离
	for (int j = 1; j < M; j++) {
   
		for (int i = 1; i <= n; i++) {
   
			for (int k = 0; k < 2; k++) {
   
				if (j == 1) {
   
					da[k][i][j] = da[k][i][j - 1] + da[1 - k][f[k][i][j - 1]][j - 1];
					db[k][i][j] = db[k][i][j - 1] + db[1 - k][f[k][i][j - 1]][j - 1];
				}
				else {
   
					da[k][i][j] = da[k][i][j - 1] + da[k][f[k][i][j - 1]][j - 1];
					db[k][i][j] = db[k][i][j - 1] + db[k][f[k][i][j - 1]][j - 1];
				}
			}
		}
	}
}

// 计算从s出发，最多行驶x距离，A和B分别行驶的距离
void calc(int s, int x, int &la, int &lb) {
   
	la = lb = 0;
	for (int i = M - 1; i >= 0; i--) {
   
		if (f[0][s][i] && la + lb + da[0][s][i] + db[0][s][i] <= x) {
   
			la += da[0][s][i];
			lb += db[0][s][i];
			s = f[0][s][i];
		}
	}
}

int main() {
   
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> n;
	for (int i = 1; i <= n; i++) cin >> h[i];

	init_g();
	init_f();
	init_d();

	int x;
	cin >> x;
	int res = 0, max_h = 0;
	double min_ra = INF;
	for (int i = 1; i <= n; i++) {
   
		int la, lb;
		calc(i, x, la, lb);
		double ra = lb ? (double) la / lb : INF;
		if (ra < min_ra || (ra == min_ra && h[i] > max_h)) {
   
			min_ra = ra;
			max_h = h[i];
			res = i;
		}
	}
	cout << res << "\n";

	int q;
	cin >> q;
	while (q--) {
   
		int s, x;
		cin >> s >> x;
		int la, lb;
		calc(s, x, la, lb);
		cout << la << " " << lb << "\n";
	}

	return 0;
}