铁球落地

Posted on In

题目来源：铁球落地

题目大意：从一个木板上往下掉，大致就是如此的模型

正解是线段树优化dp，但是我不会，

可以用比较暴力的最短路来解决

中间有很多小细节需要处理，比如我接下来与谁连边等等，处理好了可以优化很多复杂度

代码连边那里暂时没有看懂会头会补上的

题解代码如下：

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#pragma warning (disable:4996)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <deque>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 2e5 + 5, maxm = 4e5 + 5, inf = 0x7fffffff;
int head[maxm], nxt[maxm], v[maxm], w[maxm], h[maxn], x[maxn], y[maxn], dis[maxn];//h为高度，xy为左右端点
bool vis[maxn];
int n, m, cnt, sx, sy;

inline void addline(int x, int y, int z) { v[cnt] = y, w[cnt] = z, nxt[cnt] = head[x], head[x] = cnt++; }

inline int read()
{
    register int x = 0;
    register char c = getchar();
    while (c<'0' || c>'9') c = getchar();
    while (c >= '0'&&c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
    return x;
}

inline void qsort(int l, int r)//手写快排
{
    register int mid = h[(l + r) >> 1], L = l, R = r;
    while (l <= r)
    {
        while (h[l] > mid)	l++;
        while (h[r] < mid)	r--;
        if (l <= r) { swap(h[l], h[r]), swap(x[l], x[r]), swap(y[l], y[r]), l++, r--; }
    }
    if (L < r)	qsort(L, r);
    if (l < R)	qsort(l, R);
    return;
}

inline void connect()//重点操作：连边
{
    //0号为铁球，一倍点（1-n）为左端点，二倍点（n+1-2n)为右端点，2*n+1为地板（最终汇点）
    addline(0, 1, sy - h[1] + sx - x[1]), addline(0, n + 1, sy - h[1] + y[1] - sx);
    //应该是数据原因导致排序后第一块木板一定在铁球下方，所以让其和木板的左右两端点相连，假如改数据也没问题，在读入时把大于小球高度的木板全部删除，再在这个函数中按高度枚举到能接到小球的木板当成1号木板即可
    queue<int> Q;//用队列辅助链接
    while (!Q.empty())	Q.pop();
    Q.push(1);//第一块木板入队
    while (!Q.empty())
    {
        int i = Q.front(); Q.pop();
        bool left = false, right = false;//小剪枝：左右都有木板承接就可以不用枚举了
        for (int j = i + 1; h[i] > h[j] && h[i] - h[j] <= m && j <= n; j++)//暴力枚举能落下的木板
        {
            if (!left && x[j] < x[i] && x[i] < y[j])//计算木板i的左端点是否能落到木板j，根据不等式推一下就明白了
            {
                //如果可以
                addline(i, j, h[i] - h[j] + x[i] - x[j]);//木板i的左端点链接木板j的左端点
                addline(i, j + n, h[i] - h[j] + y[j] - x[i]);//木板i的左端点链接木板j的右端点（二倍点）
                left = true;
                if (!vis[j])	Q.push(j), vis[j] = true;//j没入队过才能搜，防止搜多超时
            }
            if (!right && x[j] < y[i] && y[i] < y[j])//计算木板i的右端点是否能落到木板j，与上面同理
            {
                addline(i + n, j, h[i] - h[j] + y[i] - x[j]);
                addline(i + n, j + n, h[i] - h[j] + y[j] - y[i]);
                right = true;
                if (!vis[j])	Q.push(j), vis[j] = true;
            }
            if (left && right)	break;//左右端点都有木板接着就不用枚举了
        }
        if (!left&&h[i] <= m)	addline(i, n << 1 | 1, h[i]);//如果左端点没有落点，判断能不能落到地上(点为2*n+1)
        if (!right&&h[i] <= m)	addline(i + n, n << 1 | 1, h[i]);//判断右端点，同理
    }
    return;
}

inline void SPFA()//SPFA+SLF优化
{
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    deque<int> Q;
    while (!Q.empty())	Q.pop_back();
    dis[0] = 0, Q.push_back(0), vis[0] = true;
    while (!Q.empty())
    {
        int x = Q.front(); Q.pop_front(); vis[x] = false;
        for (register int i = head[x]; i != -1; i = nxt[i])
            if (dis[v[i]] > dis[x] + w[i])
            {
                dis[v[i]] = dis[x] + w[i];
                if (!vis[v[i]])
                {
                    vis[v[i]] = true;
                    if (!Q.empty())
                    {
                        if (dis[v[i]] > dis[Q.front()])	Q.push_back(v[i]);
                        else  Q.push_front(v[i]);
                    }
                    else  Q.push_back(v[i]);
                }
            }
    }
    return;
}

int main()
{
    memset(head, -1, sizeof(head));
    n = read(), m = read(), sx = read(), sy = read();//sx,sy为小球坐标
    for (int i = 1; i <= n; i++)	h[i] = read(), x[i] = read(), y[i] = read();
    qsort(1, n), connect(), SPFA();//先排序，连接好边就跑一边SPFA
    printf("%d\n", dis[n << 1 | 1]);//最终汇点，即地板（2*n+1）离小球的最短距离即是答案
    return 0;
}

后记：

记录此题的主要目的就是发现这个题的模型十分棒，从一个与图论毫不相关的东西转换到了图论，实在是妙不可言啊！