「NOIP2012」开车旅行

传送门

Luogu

解题思路

第一步预处理每个点后面的最近点和次近点，然后就是模拟题意。

但是如果就这么搞是 \(O(N^2)\) 的，不过可以过70分，考场上也已经比较可观了。

考虑优化。

预处理最近点和次近点的过程可以用 set 优化到 \(O(n \log n)\)，也可以用双向链表优化到 \(O(n)\)。

这里介绍双向链表的做法。

把所有点装入一个结构体中，按高度降序排序。

那么我们每次取出一个点，可能更新它的最近点和次近点的点只会是它的前驱、前驱的前驱、后继、后继的后继，更新四次就好了。

然后用倍增优化一下开车的过程，具体实现看代码，因为这个就是对暴力的优化，没什么技术含量，不过细节有点多就是了。

细节注意事项

• 细节挺多的啊。。。

参考代码

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <ctime>
#define rg register
using namespace std;
template < class T > inline void read(T& s) {
s = 0; int f = 0; char c = getchar();
while (!isdigit(c)) f |= c == '-', c = getchar();
while (isdigit(c)) s = s * 10 + c - 48, c = getchar();
s = f ? -s : s;
}typedef long long LL;
const int _ = 100002;
const double eps = 1e-7;int n, r1[_], r2[_], pos[_];
struct node { int h, id, pre, nxt; } t[_];
inline bool cmp(const node& x, const node& y) { return x.h < y.h; }int r3[20][_], dis1[20][_], dis2[20][_];inline void upt(int i, int p, int j) {
if (j < 1 || j > n) return ;
LL d = abs(t[p].h - t[j].h);
LL d1 = abs(t[pos[i]].h - t[pos[r1[i]]].h);
LL d2 = abs(t[pos[i]].h - t[pos[r2[i]]].h);
if (!r1[i] || d1 > d || (d1 == d && t[j].h < t[pos[r1[i]]].h))
r2[i] = r1[i], r1[i] = t[j].id;
else if (!r2[i] || d2 > d || (d2 == d && t[j].h < t[pos[r2[i]]].h))
r2[i] = t[j].id;
}int main() {
#ifndef ONLINE_JUDGE
freopen("cpp.in", "r", stdin);
freopen("cpp.out", "w", stdout);
#endif
read(n);
for (rg int i = 1; i <= n; ++i) read(t[i].h), t[i].id = i;
sort(t + 1, t + n + 1, cmp);
for (rg int i = 1; i <= n; ++i) {
pos[t[i].id] = i;
if (i != 1) t[i].pre = i - 1;
if (i != n) t[i].nxt = i + 1;
}
for (rg int p, i = 1; i <= n; ++i) {
p = pos[i];
upt(i, p, t[p].pre);
upt(i, p, t[t[p].pre].pre);
upt(i, p, t[p].nxt);
upt(i, p, t[t[p].nxt].nxt);
if (t[p].pre) t[t[p].pre].nxt = t[p].nxt;
if (t[p].nxt) t[t[p].nxt].pre = t[p].pre;
t[p].pre = t[p].nxt = 0;
}
for (rg int i = 1; i <= n; ++i) {
r3[0][i] = r1[r2[i]];
if (r2[i])
dis1[0][i] = abs(t[pos[i]].h - t[pos[r2[i]]].h);
if (r1[r2[i]] && r2[i])
dis2[0][i] = abs(t[pos[r2[i]]].h - t[pos[r1[r2[i]]]].h);
}
for (rg int i = 1; i <= 19; ++i) {
for (rg int j = 1; j <= n; ++j) {
r3[i][j] = r3[i - 1][r3[i - 1][j]];
if (r3[i][j]) {
dis1[i][j] = dis1[i - 1][j] + dis1[i - 1][r3[i - 1][j]];
dis2[i][j] = dis2[i - 1][j] + dis2[i - 1][r3[i - 1][j]];
}
}
}
int X; read(X);
int ans = 0; double mn = 2e9;
for (rg int i = 1; i <= n; ++i) {
int x = i, s = X;
LL da = 0, db = 0;
for (rg int j = 19; ~j; --j) {
if (r3[j][x] && s >= dis1[j][x] + dis2[j][x]) {
da += dis1[j][x];
db += dis2[j][x];
s -= dis1[j][x] + dis2[j][x];
x = r3[j][x];
}
}
if (s >= dis1[0][x]) da += dis1[0][x];
if (da == 0) continue;
double nw = 1.0 * da / db;
if (!ans || mn - nw > eps || (fabs(mn - nw) <= eps && t[pos[i]].h > t[pos[ans]].h))
ans = i, mn = nw;
}
printf("%d\n", ans);
int m; read(m);
for (rg int x, s; m--; ) {
read(x), read(s);
LL da = 0, db = 0;
for (rg int j = 19; ~j; --j) {
if (r3[j][x] && s >= dis1[j][x] + dis2[j][x]) {
da += dis1[j][x];
db += dis2[j][x];
s -= dis1[j][x] + dis2[j][x];
x = r3[j][x];
}
}
if (s >= dis1[0][x]) da += dis1[0][x];
printf("%lld %lld\n", da, db);
}
return 0;
}


完结撒花 \(qwq\)