[AGC072A] Rhythm Game 题解

Description

有 NN 个按钮。第 ii 个按钮 (1≤i≤N)(1 \le i \le N) 在游戏开始后 TiT_i 秒出现在坐标 XiX_i 处。每个按钮在出现 D+0.5D + 0.5 秒后消失。

玩家从坐标 00 开始，时间为 00 ，必须按下所有 NN 按钮才能赢得游戏。按键的顺序不限。但是，在按下一个按钮后和按下另一个按钮前，玩家必须至少访问一次坐标 00 。违反此规则将被取消游戏资格。

AtCoder 女士可以在线路上以 11 的速度移动。她能赢得比赛吗？按下按钮所需的时间可以忽略不计。

解决 TESTCASES\mathrm{TESTCASES} 个测试案例。

n≤5000,∑n2≤2.5×107n\leq 5000,\sum n^2\leq 2.5\times 10^7。

Solution

首先可以对问题做个转化：第 ii 个任务在 Ti−XiT_i-X_i 时刻出现，做任务需要 2Xi2X_i 的时间，并要求必须要在 Ti+Xi+DT_i+X_i+D 时刻之前完成任务。设 Li=Ti−XiL_i=T_i-X_i，Ri=Ti+Xi+DR_i=T_i+X_i+D。

先考虑没有 LL 的限制的情况。

容易发现此时按照 RiR_i 排序一定更优，证明就考虑邻项交换，如果 Ri>Ri+1R_i>R_{i+1}，则完成 i−1i-1 号任务的最晚时刻为 min⁡(Ri−2Xi,Ri+1−2Xi−2Xi+1)=min⁡(Ri+2Xi+1,Ri+1)−2Xi−2Xi+1\min(R_i-2X_i,R_{i+1}-2X_i-2X_{i+1})=\min(R_i+2X_{i+1},R_{i+1})-2X_i-2X_{i+1}，交换后为 min⁡(Ri+1+2Xi,Ri)−2Xi−2Xi+1\min(R_{i+1}+2X_i,R_i)-2X_i-2X_{i+1}，显然交换后更优。

加上 LL 的限制后就不能直接按照 RR 排序了，因为可能出现 L2<L1<R1<R2L_2<L_1<R_1<R_2 的情况，此时如果先做 11 任务需要先等待到 L1L_1 时刻，可能会有浪费，先做 22 再做 11 则会更优。

不过如果 LL 和 RR 分别有单调性的话原来的做法是没问题的。

注意到如果先做了 RR 更大的任务 ii，则所有 Rj<RiR_j<R_i 的任务 jj 就都已经激活，因为做 ii 任务的最小结束时间为 Li+2Xi=Ti+Xi≥Tj+Xj>LjL_i+2X_i=T_i+X_i\geq T_j+X_j>L_j。此时可以把 LjL_j 看成 00，由于这些 Rj<RiR_j<R_i 的任务的 LL 和 RR 都满足单调不降的性质，所以先按照 RR 的大小顺序做这些 RR 小于 RiR_i 的任务一定更优。

具体来说，按照 RiR_i 排序后的可能操作顺序长这样：(1)(1), (2)(2), (6,3,4,5)(6,3,4,5), (8,7)(8,7), (9)(9), (10)(10)。

设 fif_i 表示做完前 ii 个任务的最小时间，然后枚举下一个做的任务即可。

时间复杂度：O(n2)O(n^2)。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>

// #define int int64_t

using i64 = int64_t;

const int kMaxN = 5e3 + 5;
const i64 kInf = 1e18;

int n;
i64 d, t[kMaxN], x[kMaxN], id[kMaxN], l[kMaxN], r[kMaxN];
i64 f[kMaxN], s[kMaxN], g[kMaxN][kMaxN];

void getg() {
  for (int i = 1; i <= n; ++i) {
    i64 sum = 0;
    g[i][i - 1] = kInf;
    for (int j = i; j <= n; ++j) {
      sum += 2 * x[id[j]];
      g[i][j] = std::min(g[i][j - 1], r[j] - sum);
    }
  }
}

void dickdreamer() {
  std::cin >> n >> d;
  for (int i = 1; i <= n; ++i) {
    std::cin >> t[i] >> x[i];
    id[i] = i;
  }
  std::sort(id + 1, id + 1 + n, [&] (int i, int j) { return t[i] + x[i] < t[j] + x[j]; });
  for (int i = 1; i <= n; ++i) {
    l[i] = t[id[i]] - x[id[i]], r[i] = t[id[i]] + x[id[i]] + d;
    s[i] = s[i - 1] + 2 * x[id[i]];
    // std::cerr << id[i] << ' ' << l[i] << ' ' << r[i] << '\n';
  }
  getg();
  f[0] = 0, std::fill_n(f + 1, n, kInf);
  for (int i = 0; i < n; ++i) {
    // std::cerr << i << ' ' << f[i] << '\n';
    for (int j = i + 1; j <= n; ++j) {
      i64 now = std::max(f[i], l[j]) + 2 * x[id[j]];
      // if (i == 0 && j == 2) std::cerr << "??? " << now << '\n';
      if (now <= r[j] && now <= g[i + 1][j - 1]) f[j] = std::min(f[j], now + s[j - 1] - s[i]);
    }
  }
  std::cout << (f[n] != kInf ? "Yes\n" : "No\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;
}
[AGC072A] Rhythm Game 题解
https://sobaliuziao.github.io/2025/04/21/post/67089132.html
作者
Egg_laying_master
发布于
2025年4月21日
许可协议