题解：CF1463C Busy Robot

Bc2_Ch1ckenPr1nce · 2025-12-06 09:15:16 · 题解

Sol

其实是一个比较简单的模拟。

首先如果按时间线枚举肯定是不行的，会达到 10^9 量级。

所以我们可以枚举命令。

我们可以用两个变量 x_0, t_0 存储当前处理的命令的 t 和 x，初始时 x_0 = t_0 = 0，并用一个变量 p 存储当前位置。

然后开始枚举命令，判断一下当前命令有没有被忽略。一个任务未被忽略当且仅当 t_i \ge |p - x_0| + t_0，也就是说当前时间大于上一个未被忽略的命令的完成时间。由于移动速度是 1，所以移动的时间就是位置差。

如果这个命令未被忽略，那么就判断是否在下一个命令开始前是否能移动到（当且仅当 t_{i + 1} - t_i \ge |x_0 - x_i|），如果能答案 +1。最后记得更新 t_0, x_0。

如果这个命令被忽略，那么就看看在 [t_i, t_{i + 1}] 这段时间内能移动到的位置 [l, r] 是否有 x_i \in [l, r]，如果有答案就 +1。这个公式就不写了，有点长。

最后，一定要记得把 t_{n + 1} 设成大一点的数，最好是 9 \times 10^{18}！

Code

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ull = unsigned long long;

const int kMaxN = 1e5 + 10;

ll n, t[kMaxN], x[kMaxN], nt, nx, pos, ans;

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int tt;
  for (cin >> tt; tt; -- tt) {
    cin >> n, t[n + 1] = 9e18;
    for (int i = 1; i <= n; ++ i) {
      cin >> t[i] >> x[i];
    }
    nt = nx = pos = ans = 0;
    for (int i = 1; i <= n; ++ i) {
      if (t[i] >= abs(pos - nx) + nt) {
        pos = nx;
        if (t[i + 1] - t[i] >= abs(nx - x[i])) {
          ++ ans;
        }
        nt = t[i], nx = x[i];
      } else {
        if (pos >= nx) {
          if (pos - (t[i] - nt) >= x[i] && pos - (t[i + 1] - nt) <= x[i] && pos >= x[i] && nx <= x[i]) {
            ++ ans;
          }
        } else {
          if (pos + (t[i] - nt) <= x[i] && pos + (t[i + 1] - nt) >= x[i] && pos <= x[i] && nx >= x[i]) {
            ++ ans;
          }
        }
      }
    }
    cout << ans << '\n';
  }
  return 0;
}