题解：AT_abc434_c [ABC434C] Flapping Takahashi

hyc1207 · 2025-11-30 11:37:03 · 题解

题目大意

高桥初始在高度 H(1\le H\le10^9)，每秒最多飞行 1 个高度、他有 N(1\le N\le10^5) 个目标，第 i 个目标要求他在 t_i(1\le t_i\le10^9) 时刻，高度在 l_i 和 u_i 之间。他在飞行时高度不能低于或等于 0。请判断他能否达到所有目标。

思路

对于每一次的飞行，我们可以根据 t_i 判断他可以飞行的范围，如果该范围与 [l_i,u_i] 有交集，表示可以达到第 i 个目标，否则不能达到。

具体来说，可以使用一个范围 [l,r] 来表示高桥在当前情况下可以飞行的范围，最初 l 和 r 都为 0。由于题目已经对 t_i 排好序，接着可以直接枚举每一个目标，此时他能达到的最低高度为 \max(1,l-(t_i-t_{i-1}))，能达到的最高高度为 r+(t_i-t_{i-1})，如果他能达到的最低高度仍然高于目标的上限，或最高高度仍然低于目标下限，即 l>u_i 或 r<l_i，则他不能达到该目标，直接返回结果并退出循环。如果他能达到该目标，将此时的飞行区间更新为目前可飞行高度区间 [\max(1,l-(t_i-t_{i-1})),r+(t_i-t_{i-1})] 与目标区间 [l_i,u_i] 的交集，也就是 [\max(\max(1,l-(t_i-t_{i-1})),l_i),\min(r+(t_i-t_{i-1}),u_i)]。

最终时间复杂度为枚举区间的时间复杂度 O(N)。

AC Code

#include <iostream>
using namespace std;
const int N = 1e5+5;
struct Target //目标
{
    int t,l,u;
}tar[N];
int n;
bool check(int h)
{
    int l = h, r = h;
    for (int i = 1; i <= n; i++)
    {
        int d = tar[i].t-tar[i-1].t;
        if (r+d < tar[i].l || l-d > tar[i].u) return 0;
        l = max(1,max(tar[i].l,l-d));
        r = min(tar[i].u,r+d);
    }
    return 1;
}
int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        int h;
        cin >> n >> h;
        for (int i = 1; i <= n; i++) cin >> tar[i].t >> tar[i].l >> tar[i].u;
        tar[0] = {0,h,h};
        if (check(h)) cout << "Yes\n";
        else cout << "No\n";
    }
    return 0;
}