[AGC072A] Rhythm Game

Genius_Star · 2026-08-31 15:02:23 · 题解

或许更好的阅读体验。

思路：

牛逼题，拜谢 jds 场上秒了这题。

因为每次按了都要回来，所以对于一个按钮是可以单独考虑的，考虑收集这个按钮出发时间的限制，显然必须在 [t_i - x_i, t_i + d - x_i]（可以更早出发，但是显然没必要，因为恰好更充分利用时间）这个区间内出发才可以恰好收集到这个按钮，然后来回跑两次需要花 2x_i 的时间，于是最多在 t_i + d + x_i 的时间要回到原点。

于是可以看作在 [t_i - x_i, t_i + d + x_i] 中选择一个长度为 2x_i 的区间，要去和其它按钮选择的区间不交，是否有合法方案。

可以看作有若干个任务，第 i 个任务在 l_i = t_i - x_i 时刻派发，做这个任务需要 tim_i = 2x_i 的时间，且需要在 r_i = t_i + d + x_i 前完成，问是否能做 n 个任务。

看起来很难做啊，能不能找一些性质，如果 l_i 都是 0 的话，一个显然的贪心是按照 r_i 从小到大依次做任务，能做就做，因为如果 r_i > r_j 且先做的 r_i 的任务再做 r_j 的，那么显然交换做的顺序后依然合法且不劣。

现在加上 l 的限制了，依然按照 r 排序，但是上面那个贪心策略就会有问题，因为可能出现 r_i 最小的任务还没有发布，空闲时间内应该去做其它已经发布了的任务，那这个策略怎么刻画呢？

假设空闲时间内去做了任务 j，你会发现做完 j 之后所有 i < j 的任务一定都发布了，那是因为 t_j + x_j + d \ge t_i + x_i + d，考察做完 j 的最早时间显然是 t_j + x_j \ge t_i + x_i \ge t_i - x_j，得证。

那么根据前面的贪心策略，空闲时间内如果先做了 j 任务了，那么 j 前面的任务一定已经发布了，应该按照 r 的大小从小到大依次做，直到最小的 r 任务又没有发布，那就先去做另外一个任务，然后这个任务前面的都会发布，以此类推……

上面那个过程显然可以用 dp 刻画，定义 f_i 表示完成了前 i 个任务所需要的最小时间，然后找一个 j 去完成任务 j 后发布了 <j 的任务，再依次去完成 i + 1, \cdots, j - 1，于是：

然后考虑怎么算中间的是否能全部完成，显然做完 j 后的时间是 t = \max(l_j, f_i) + tim_j，然后依次做 [i + 1, j - 1]，设当前做到 k，需要满足 t + \sum_{i + 1 \le x \le k} tim_x \le r_k，令 s 为 tim 前缀和，相当于满足 t + s_k - s_i \le r_k，即 t - s_i \le r_k - s_k；于是只需要找到中间 k 的 r_k - s_k 的最小值即可快速 check，枚举 i 的时候顺路处理即可。

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

完整代码：

#include<bits/stdc++.h>
#define fi first
#define se second
#define lowbit(x) x & (-x)
using namespace std;
typedef long long ll;
const int N = 5050;
const ll inf = 1e18;
inline ll read(){
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')
          f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
} 
inline void write(ll x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
      write(x / 10);
    putchar(x % 10 + '0');
}
struct Node{
    ll l, r, tim;
    inline bool operator<(const Node&rhs)const{
        if(r ^ rhs.r)
          return r < rhs.r;
        if(l ^ rhs.l)
          return l < rhs.l;
        return tim < rhs.tim;
    }
}a[N];
int T, n;
ll x, t, d;
ll s[N], dp[N];
inline void solve(){
    n = read(), d = read();
    for(int i = 1; i <= n; ++i){
        t = read(), x = read();
        a[i] = {t - x, t + d + x, x * 2ll};
        a[i].l = max(a[i].l, 0ll);
    }
    sort(a + 1, a + n + 1);
    for(int i = 1; i <= n; ++i)
      s[i] = s[i - 1] + a[i].tim;
    for(int j = 1; j <= n; ++j){
        // cerr << a[j].l << ' ' << a[j].r << ' ' << a[j].tim << '\n';
        ll mn = inf;
        dp[j] = inf;
        for(int i = j - 1; i >= 0; --i){
            if(dp[i] == inf){
                if(i != j - 1)
                  mn = min(mn, a[i + 1].r - s[i + 1]);
                continue;                
            }
            ll t = max(a[j].l, dp[i]) + a[j].tim;
            if(t > a[j].r){
                if(i != j - 1)
                  mn = min(mn, a[i + 1].r - s[i + 1]);
                continue;
            }
            if(i != j - 1)
              mn = min(mn, a[i + 1].r - s[i + 1]);
            if(t - s[i] <= mn){
                // cerr << j << ' ' << i << ' ' << t << ' ' << mn << '\n';
                dp[j] = min(dp[j], t + s[j - 1] - s[i]);
            }
            // cerr << a[i + 1].r - s[i + 1] << '\n';
        }
        // cerr << dp[j] << '\n';
    }
    if(dp[n] == inf)
      puts("No");
    else
      puts("Yes");
}
int main(){
    T = read();
    while(T--)
      solve();
    return 0;
}