P9521 [JOISC 2022] 京都观光 题解

Description

有一个 $n\times m$ 的网格，从 $(x,y)$ 走到 $(x,y+1)$ 需要 $a_x$ 的时间，从 $(x,y)$ 走到 $(x+1,y)$ 需要 $b_y$ 的时间。

问从 $(1,1)$ 走到 $(n,m)$ 至少需要多久。

$1\leq n,m\leq 10^5$。

Solution

首先直接做不太好做，考虑调整法。

容易发现 $(i,j)\to (k,l)$ 有两种走法：

1. $(i,j)\to (i,l)\to (k,l)$
2. $(i,j)\to (k,j)\to (k,l)$

其中第一个代价为 $c_1=a_i\cdot(l-j)+b_l\cdot(k-i)$，第二个代价为 $c_2=a_k\cdot(l-j)+b_j\cdot (k-i)$，如果 $c_1\leq c_2$，移项后可得：$(b_l-b_j)\cdot(k-i)\leq(a_k-a_i)\cdot(l-j)$，等价于 $\displaystyle\frac{b_l-b_j}{l-j}\leq\frac{a_k-a_i}{k-i}$。

容易发现把路径折线缩起来后，这些线段在坐标系上的斜率不降。

所以如果知道 $x$ 和 $y$ 分别走的连续段，那么每次选择 $x$ 和 $y$ 里能走的斜率更小的去走。

现在考虑怎么缩连续段。

先考虑 $x$。首先是有 $n$ 个连续段，如果存在相邻连续段满足第一个大于等于第二个，则由于每次选的是斜率更小的走，所以选了第一个之后一定紧接的是第二个，这两段就能缩在一起。

同时如果对于一个连续段，能够让其从中间劈开后满足斜率不降，则贪心地劈开一定更优。

容易发现满足这个条件的连续段劈法就是所有 $(i,a_i)$ 构成的凸包。

分别求出 $a$ 和 $b$ 的凸包即可。

时间复杂度：$O(n+m)$。

Code

#include <bits/stdc++.h>

// #define int int64_t

using i64 = int64_t;
using pii = std::pair<int, int>;

const int kMaxN = 1e5 + 5;

int n, m, topa, topb;
int a[kMaxN], b[kMaxN];
pii stka[kMaxN], stkb[kMaxN];

pii sub(pii a, pii b) { return {a.first - b.first, a.second - b.second}; }
i64 mul(pii a, pii b) { return 1ll * a.first * b.second - 1ll * a.second * b.first; }

void geta() {
  for (int i = 1; i <= n; ++i) {
    pii p = {i, a[i]};
    for (; topa >= 2 && mul(sub(p, stka[topa]), sub(stka[topa], stka[topa - 1])) >= 0; --topa) {}
    stka[++topa] = p;
  }
}

void getb() {
  for (int i = 1; i <= m; ++i) {
    pii p = {i, b[i]};
    for (; topb >= 2 && mul(sub(p, stkb[topb]), sub(stkb[topb], stkb[topb - 1])) >= 0; --topb) {}
    stkb[++topb] = p;
  }
}

void dickdreamer() {
  std::cin >> n >> m;
  for (int i = 1; i <= n; ++i) std::cin >> a[i];
  for (int i = 1; i <= m; ++i) std::cin >> b[i];
  geta(), getb();
  int x = 1, y = 1;
  i64 ans = 0;
  for (int i = 1, j = 1; x < n || y < m;) {
    bool nxt = 0;
    if (x == n || y < m && mul(sub(stkb[j + 1], stkb[j]), sub(stka[i + 1], stka[i])) >= 0) nxt = 1;
    if (!nxt) {
      ans += 1ll * b[y] * (stka[i + 1].first - stka[i].first);
      x += stka[i + 1].first - stka[i].first;
      ++i;
    } else {
      ans += 1ll * a[x] * (stkb[j + 1].first - stkb[j].first);
      y += stkb[j + 1].first - stkb[j].first;
      ++j;
    }
  }
  std::cout << ans << '\n';
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}