P1442 铁球落地

· · 题解

写在前面

我没用线段树（躲进小被几.jpg）

思路

球是从上往下掉落的啊，所以按高度从高到低排序

从哪个平台开始是可以确定的，一开始比球高的平台就直接略过，然后再找能接到球的第一个平台，设下标为 now，

设 c[i].l 和 c[i].r 分别表示到某个平台的左边缘、右边缘所耗时间（因为小球掉落的垂直距离是一定的，所以所以这里 c 数组只记录水平所耗时间）

从 now 枚举到 n，考虑当前枚举到的平台从左、右两边缘分别掉到哪里，就更新哪个平台的值，所以每个平台的两边缘只需找到第一个接到球的平台就好了，考虑到一个平台能接受到从不同平台的边缘掉落的球，所以更新时取max，所以事先将 c 数组赋最大值

注意

至于为什么暴力能过，大概因为平台过于密集导致该平台与其第一个接到球的平台距离过近，而我偷鸡取巧，不排除数据水的原因（？雾）

代码有注释，不懂请私信 

#include <bits/stdc++.h>
#define N 100010
#define inf 999999999
using namespace std;
inline int in() {
    int x = 0, f = 1; char C = getchar();
    while(C < '0' or C > '9') { if(C == '-') f = -1; C = getchar(); }
    while(C >= '0' and C <= '9') x = (x << 3) + (x << 1) + (C ^ 48), C = getchar();
    return x * f;
}
int n, H, sx, sy, ans = inf;
struct hh { int h, l, r; } o[N];
struct hhh { int l, r; } c[N];
bool cmp(hh x, hh y) { return x.h > y.h; }
// H：掉落高度限制 o：记录平台信息 c:记录到第i个平台左右边缘分别所耗最短时间

int main() {
    n = in(), H = in(), sx = in(), sy = in();
    for(int i = 1; i <= n; i ++) o[i].h = in(), o[i].l = in(), o[i].r = in();
    for(int i = 1; i <= n; i ++) c[i].l = c[i].r = inf; //初始化
    sort(o + 1, o + n + 1, cmp); 
    //从下面开始找第一个接到球的平台
    int now = 1;
    while(sy < o[now].h) now ++; //比球高的略过
    while(sx > o[now].r or sx < o[now].l) now ++; //直到能接到球为止
    c[now].l = sx - o[now].l; //只考虑水平方向的耗时
    c[now].r = o[now].r - sx;
    for(register int i = now, oo, flag; i <= n; i ++) {
        if(c[i].l == inf) continue; //球没能到达过此平台，自然无法更新别人，跳过
    //左边缘↓
        oo = i + 1, flag = 1; 
        //oo：枚举i之后的平台的下标，直到找到第一个能接住从第i个平台左边缘掉落的球的平台
        //flag：若从左边缘掉落能更新到某个平台，不能掉到地上，赋为0
        while(o[i].h - o[oo].h <= H and oo <= n) {//掉落高度限制内&&n个内
            if(o[oo].l <= o[i].l and o[i].l <= o[oo].r) {//若能接到
                c[oo].l = min(c[oo].l, c[i].l + o[i].l - o[oo].l);
                c[oo].r = min(c[oo].r, c[i].l + o[oo].r - o[i].l);
                flag = 0; break;//能更新到别人，赋0，退出
            } oo ++;
        }
        if(o[i].h <= H and flag) ans = min(ans, c[i].l);
        //若没有平台能接到球，且在H范围内，就可以更新答案了
        //右边缘↓，ctrl+c and ctrl+v and 微创
        oo = i + 1, flag = 1;
        while(o[i].h - o[oo].h <= H and oo <= n) {
            if(o[oo].l <= o[i].r and o[i].r <= o[oo].r) {
                c[oo].l = min(c[oo].l, c[i].r + o[i].r - o[oo].l);
                c[oo].r = min(c[oo].r, c[i].r + o[oo].r - o[i].r);
                flag = 0; break;
            } oo ++;
        }
        if(o[i].h <= H and flag) ans = min(ans, c[i].r);
    }
    cout << ans + sy;//水平移动耗时+初始高度
    return 0;
}