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

· · 题解

本题解借助 STL map 维护每个城市后续所有城市的海拔和编号，来预处理 A 和 B 二人各自对旅途中每个城市下一站的决策（分别对应变量 A 和 B），总开销 O(n\log n)，虽然常数稍大，但实现较为简单方便。

具体地，设 \mathrm{heights} 为当前城市后续所有城市的海拔向编号的映射，类型为 map<int, int>，初始化为空。 从右向左遍历每个城市，根据当前城市的海拔，利用 upper_bound 方法找到后续城市中海拔更高且最接近的城市（或因找不到而得到 \mathrm{heights.end()}），然后在边界范围内扩展至左右长度（以增减迭代器计）均不超过 2 的邻域，此时可以确定该邻域一定包含了可能的最近和次近城市，在其范围内搜索即可确定答案。以上流程处理完毕后将当前城市加入 \mathrm{heights} 中，以供后续迭代步骤使用。

在此基础上，可以从 i = 0 开始倍增出由 A 先开车，连续访问后续 2^i 个城市，最终将到达的城市以及 A 和 B 各自行驶的距离。后续只需借助倍增结果进行模拟和简单枚举，便可快速得到答案，总的复杂度是 O((n + m)\log n)。

#include <algorithm>
#include <iostream>
#include <map>
#include <vector>

using namespace std;

#define long long long

int n;
vector<int> H;  // 海拔
vector<int> A;  // 第二近的后续城市下标
vector<int> B;  // 最近的后续城市下标

// 存储终点和 A, B 各自行驶的距离
vector<vector<tuple<int, long, long>>> AD;  // [i, j] -> A 从 j 出发，走 2^i 步
vector<vector<tuple<int, long, long>>> BD;  // [i, j] -> B 从 j 出发，走 2^i 步

void init()
{
  // 预处理 A 和 B 在每个位置处的选择
  A.resize(n), B.resize(n);
  A[n - 1] = B[n - 1] = -1;

  // 维护当前城市所有后续城市海拔的有序集合
  map<int, int> heights;  // [height] -> index
  heights.emplace(H[n - 1], n - 1);

  for(int i = n - 2; i >= 0; --i) {
    // 寻找距离最近和第二近的可达位置
    vector<pair<long, int>> cands;              // 最近和次近候选 (dist, index)
    cands.reserve(4);                           // 最多搜索 4 个元素
    auto r = heights.upper_bound(H[i]), l = r;  // 确定搜索邻域中心
    if(r != heights.end()) ++r;                 // 确定搜索范围
    if(r != heights.end()) ++r;
    if(l != heights.begin()) --l;
    if(l != heights.begin()) --l;
    for(; l != r; ++l) {
      long dist = (labs(l->first - H[i]) << 1) | (l->first > H[i]);  // 低海拔优先
      cands.emplace_back(dist, l->second);
    }
    if(cands.size() > 1) nth_element(cands.begin(), cands.begin() + 1, cands.end());
    B[i] = cands[0].second;
    A[i] = cands.size() > 1 ? cands[1].second : -1;
    //cout << "A: " << i + 1 << " -> " << A[i] + 1 << endl;
    //cout << "B: " << i + 1 << " -> " << B[i] + 1 << endl;
    heights.emplace(H[i], i);
  }

  // 倍增起点：走 2^0 步
  int log_l = 31 - __builtin_clz(max(n - 1, 1));
  AD.resize(log_l + 1), BD.resize(1);  // BD 在后续不会用到，不需倍增
  AD[0].assign(n, { -1, 0, 0 }), BD[0].assign(n, { -1, 0, 0 });
  for(int j = 0; j < n - 1; ++j) {
    if(A[j] >= 0) AD[0][j] = { A[j], abs(H[j] - H[A[j]]), 0 };
    if(B[j] >= 0) BD[0][j] = { B[j], 0, abs(H[j] - H[B[j]]) };
  }

  // 倍增
  for(int i = 1; i <= log_l; ++i) {
    AD[i].assign(n, { -1, 0, 0 });
    for(int j = 0; j < n - (1 << i); ++j) {
      auto [at, aa, ab] = AD[i - 1][j];
      if(at < 0) continue;
      auto [bt, ba, bb] = i == 1 ? BD[i - 1][at] : AD[i - 1][at];
      AD[i][j] = { bt, aa + ba, ab + bb };
    }
  }
}

// 给定起点和最长行驶距离，计算 A 和 B 各自的行驶距离
pair<long, long> compute(int s, int x)
{
  long ca = 0, cb = 0;
  for(int i = AD.size() - 1; i >= 0; --i) {  // 走 2^i 步
    auto [t, a, b] = AD[i][s];               // 保证永远都到 A 开车
    if(t < 0) continue;
    if(a + b > x) continue;
    x -= a + b;
    s = t;
    ca += a, cb += b;
  }
  return { ca, cb };
}

void solve(int x)
{
  int sm = 0;
  auto [cam, cbm] = compute(sm, x);
  //cout << sm << ": " << cam << " : " << cbm << endl;
  for(int s = 1; s < n; ++s) {
    auto [ca, cb] = compute(s, x);
    //cout << s << ": " << ca << " : " << cb << endl;
    if(cb == 0 && cbm == 0) {  // 均为正无穷
      if(H[s] > H[sm]) sm = s, cam = ca, cbm = cb;
    } else if(cb == 0) {  // 原来非正无穷，现在为正无穷
      // 空
    } else if(cbm == 0) {  // 原来为正无穷，现在非正无穷
      sm = s, cam = ca, cbm = cb;
    } else {  // 均非正无穷
      __int128_t u = (__int128_t)ca * cbm, v = (__int128_t)cb * cam;
      if(u < v || (u == v && H[s] > H[sm])) sm = s, cam = ca, cbm = cb;
    }
  }
  cout << sm + 1 << endl;
}

void solve(int s, int x)
{
  auto [ca, cb] = compute(s, x);
  cout << ca << " " << cb << endl;
}

int main()
{
  cin.tie(0)->sync_with_stdio(0);
  cin >> n;
  H.resize(n);
  for(int &h : H) cin >> h;
  int x;
  cin >> x;
  init();
  solve(x);
  int m;
  cin >> m;
  while(m--) {
    int s;
    cin >> s >> x, --s;
    solve(s, x);
  }
  return 0;
}

更新记录

25/1/9 01:26 更新对“正无穷”比例的特判

感谢 这篇帖子 提供的参考。注意题目中所规定的“正无穷”比例，包括任意整数比零，特别是包括零比零。

给审核人员添麻烦了。