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