LOJ #2392. 「JOISC 2017 Day 1」烟花棒 题解

Description

有 $N$ 人站在一条数轴上。他们人手一个烟花，每人手中的烟花都恰好能燃烧 $T$ 秒。每个烟花只能被点燃一次。

$1$ 号站在原点，$i$ 号 $(1\le i\le N)$ 到 $1$ 号的距离为 $X_i$。保证 $X_1=0,$ $X_1, X_2, \dots, X_N$ 单调递增（可能有人位置重叠）。

开始时， $K$ 号的烟花刚开始燃烧,，其他人的烟花均未点燃。他们的点火工具坏了，只能用燃着的烟花将未点燃的烟花点燃。当两人位置重叠且其中一人手中的烟花燃着时，另一人手中的烟花就可以被点燃。忽略点火所需时间。

求至少需要以多快的速度跑，才能点燃所有人的烟花（此时可能有些人的烟花已经熄灭了）。速度必须是一个非负整数。

$1\le K, N \le 10^5, 1\le T\le 10^9, 0\le X_i\le 10^9 (1\le i\le N), X_1 = 0, \{X_N\}$ 单调递增。

Solution

显然是二分答案，考虑怎么 check。

首先没点燃的人一定是向 $k$ 方向走。

有个关键结论是一个点燃的人碰到一个没点燃的人的时候是不会先点燃的，而是两个人一起走，等一个烟花即将熄灭时再续上。

证明就考虑设那个点燃的烟花剩余时间是 $t$，相遇位置是 $x$，如果瞬间点燃并同向走显然不优。如果反向走，则可以点燃 $[x-2tv,x+2Tv]$ 内的烟花。两个人先一起往左走，可以点燃 $[x-2tv,x]$ 内的烟花，此时续上并往右走，由于右边在前 $t$ 的时间内是和两个人速度完全一致，所以它们相对位置不变，往右则能够点燃 $[x,x+2Tv]$ 内的烟花，和瞬间点燃是一样的。

容易发现按照上面的策略，每次被点燃过的烟花一定是一段区间 $[L,R]$，且刚点到 $[L,R]$ 的时候剩余总时间是 $t(R-L)-\frac{x_R-x_L}{2v}$，只要每次区间往左右拓展时这个东西始终是非负的即可。

也就是 $2tv(R-L)-(x_R-x_L)=(2tvR-x_R)-(2tvL-x_L)\geq 0$，设 $a_i=2Tvi-x_i$，则需要满足 $a_L\leq a_R$。

现在问题变为有个初始区间 $[k,k]$，每次可以拓展左右端点，要求任意时刻都要满足 $a_L\leq a_R$，问能不能走到。这是这道题，可以直接套用做法。

不过还有个做法是令 $f(L,R)=2tv(R-L)-(x_R-x_L)$，每次往左右拓展贪心选更大的显然不对，但是会发现往一侧拓展时如果目前贡献为负数是不会停止的，否则一开始就往另一边走或者一直走直到这边贡献非负一定更优。

所以我们可以找到分别往左右拓展第一次能让贡献非负的位置，然后贪心地选择目前能拓展的贡献更大的一边拓展即可。

但是如果当前局面两边都只能为负数，就不太能做了。注意到最终状态是固定的，所以再时空倒流就能保证总有一边贡献非负了。

时间复杂度：$O(n\log V)$。

Code

#include <bits/stdc++.h>

#define int int64_t

const int kMaxN = 1e5 + 5;

int n, k, T;
int x[kMaxN], a[kMaxN];

std::tuple<int, int, int> getl(int p, int v) {
  if (p < 1) return {0, 0, 0};
  int mi = 0, s = 0, now = 0;
  for (int i = p; i; --i) {
    now = std::min<int>(now, 0) + 2 * v * T - (x[i + 1] - x[i]);
    mi = std::min(mi, now);
    s += 2 * v * T - (x[i + 1] - x[i]);
    if (s >= 0) return {p - i + 1, mi, s};
  }
  // return {1, std::min<int>(2 * v * T - (x[p + 1] - x[p]), 0), 2 * v * T - (x[p + 1] - x[p])};
  return {p, mi, s};
}

std::tuple<int, int, int> getr(int p, int v) {
  if (p > n) return {0, 0, 0};
  int mi = 0, s = 0, now = 0;
  for (int i = p; i <= n; ++i) {
    now = std::min<int>(now, 0) + 2 * v * T - (x[i] - x[i - 1]);
    mi = std::min(mi, now);
    s += 2 * v * T - (x[i] - x[i - 1]);
    if (s >= 0) return {i - p + 1, mi, s};
  }
  // return {1, std::min<int>(2 * v * T - (x[p] - x[p - 1]), 0), 2 * v * T - (x[p] - x[p - 1])};
  return {n - p + 1, mi, s};
}

std::tuple<int, int, int> getl1(int p, int lim, int v) {
  if (p < lim) return {0, 0, 0};
  int mi = 0, s = 0, now = 0;
  for (int i = p; i >= lim; --i) {
    now = std::min<int>(now, 0) - (2 * v * T - (x[i + 1] - x[i]));
    mi = std::min(mi, now);
    s -= 2 * v * T - (x[i + 1] - x[i]);
    if (s >= 0) return {p - i + 1, mi, s};
  }
  // return {1, std::min<int>(2 * v * T - (x[p + 1] - x[p]), 0), 2 * v * T - (x[p + 1] - x[p])};
  return {p - lim, mi, s};
}

std::tuple<int, int, int> getr1(int p, int lim, int v) {
  if (p > lim) return {0, 0, 0};
  int mi = 0, s = 0, now = 0;
  for (int i = p; i <= lim; ++i) {
    now = std::min<int>(now, 0) - (2 * v * T - (x[i] - x[i - 1]));
    mi = std::min(mi, now);
    s -= 2 * v * T - (x[i] - x[i - 1]);
    if (s >= 0) return {i - p + 1, mi, s};
  }
  // return {1, std::min<int>(2 * v * T - (x[p] - x[p - 1]), 0), 2 * v * T - (x[p] - x[p - 1])};
  return {lim - p + 1, mi, s};
}

bool check(int v) {
  int L = k, R = k, now = 0;
  auto [lenl, mil, sl] = getl(k - 1, v);
  auto [lenr, mir, sr] = getr(k + 1, v);
  for (; L != 1 || R != n;) {
    // std::cerr << "fuck " << L << ' ' << R << ' ' << now << '\n';
    // std::cerr << lenl << ' ' << mil << ' ' << sl << ' ' << lenr << ' ' << mir << ' ' << sr << '\n';
    if (sl < 0 && sr < 0) break;
    if (!lenl || lenr && now + mir >= 0 && (now + mil < 0 || sl < sr)) {
      if (now + mir < 0) return 0;
      now += sr, R += lenr;
      std::tie(lenr, mir, sr) = getr(R + 1, v);
    } else {
      if (now + mil < 0) return 0;
      now += sl, L -= lenl;
      std::tie(lenl, mil, sl) = getl(L - 1, v);
    }
  }
  if (L == 1 && R == n) return 1;
  int nl = 1, nr = n;
  std::tie(lenl, mil, sl) = getr1(nl + 1, L, v);
  std::tie(lenr, mir, sr) = getl1(nr - 1, R, v);
  now = 2 * (n - 1) * v * T - (x[n] - x[1]);
  if (now < 0) return 0;
  for (; nl != L || nr != R;) {
    // std::cerr << L << ' ' << R << ' ' << nl << ' ' << nr << ' ' << lenl << ' ' << mil << ' ' << sl << ' ' << lenr << ' ' << mir << ' ' << sr << '\n';
    // assert(sl >= 0 || sr >= 0);
    if (!lenl || lenr && now + mir >= 0 && (now + mil < 0 || sl < sr)) {
      if (now + mir < 0) return 0;
      now += sr, nr -= lenr;
      std::tie(lenr, mir, sr) = getl1(nr - 1, R, v);
    } else {
      if (now + mil < 0) return 0;
      now += sl, nl += lenl;
      std::tie(lenl, mil, sl) = getr1(nl + 1, L, v);
    }
  }
  // std::cerr << "fuck " << L << ' ' << R << ' ' << now << '\n';
  // std::cerr << lenl << ' ' << mil << ' ' << sl << ' ' << lenr << ' ' << mir << ' ' << sr << '\n';
  return 1;
}

void dickdreamer() {
  std::cin >> n >> k >> T;
  for (int i = 1; i <= n; ++i) std::cin >> x[i];
  int L = -1, R = 1e9, res = 1e9;
  while (L + 1 < R) {
    int mid = (L + R) >> 1;
    if (check(mid)) R = res = mid;
    else L = mid;
  }
  std::cout << res << '\n';
  // check(173187);
}

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