洛谷 P1105 平台 题解

原题链接点这里

题目描述

空间中有一些平台。给出每个平台的位置，请你计算从每一个平台的边缘落下之后会落到哪一个平台上。注意，如果某两个平台的某个两边缘横坐标相同，物体从上面那个平台落下之后将不会落在下面那个平台上。平台不会重叠，不会有两个平台的边缘碰在一起。

如果有两个平台的高度相同且都可以被落到的话，那么会落到编号靠前的那个平台。

输入格式

第一行有一个数 $N$ 表示平台的个数;

接下来 $N$ 行每行三个整数 分别是平台的高度 $H_i$，左端点的 $X$ 坐标 $L_i$，右端点的 $X$ 坐标 $R_i$。

其中，$1 \le N \le {10}^3$，$0 \le H,L,R \le 2 \times {10}^4$。

输出格式

输出共 $N$ 行，每行两个数，分别表示：

从第 $i$ 个平台的左边缘落下后到达的平台序号和右边缘落下以后到达的平台序号。

输入数据中第一个平台的序号是 $1$。如果某个平台的某个边缘下面没有平台了，输出 $0$。

样例 #1

样例输入 #1

5
2 0 2
4 1 3
3 1 3
5 3 4
1 1 5

样例输出 #1

0 5
1 5
1 5
5 5
0 0

提示

讲解

• 考点有结构体排序，构建结构体。
• 这里一个物体有不同属性，我们考虑用结构体来存储属性。
• 这里我们首先对高度进行排序，因为跳下去肯定是落到比它低的平台上，所以我们把平台先按高度进行排序，题目中说明了如果高度相同就落到编号靠前的平台。
• 注意：结构体排序的时候，cmp的形式参数要声名结构体名称,而不是int。例如bool cmp1(node x, node y)。
• 从高度最高开始遍历，向左跳的时候，下一个平台j的左边界小于i的左边界，平台j的右边界大于i的左边界，就能从i平台跳到j平台。向右跳同理。
• 最后因为要从平台1开始输出，所以再根据平台序号排一下序，然后再输出就行了。
  

源代码

#include <bits/stdc++.h>

using namespace std;

#define LL long long

#define endl "\n"

const int N = 1e5 + 10;

const int M = 1001;

int n;

struct node
{
    int h, l, r, id, ansl, ansr;

}c[10010];

bool cmp1(node x, node y)
{
    if (x.h == y.h)
    {
        return x.id< y.id;
    }
    else
    {
        return x.h > y.h;
    }
}

bool cmp2(node x, node y)
{
    return x.id < y.id;
}

void solve()
{
    cin >> n;

    for (int i = 1; i <= n; i ++ )
    {
        c[i].id = i;
        cin >> c[i].h >> c[i].l >> c[i].r;
    }

    sort(c + 1, c + 1 + n, cmp1);

    for (int i = 1; i <= n; i ++)
    {
        for (int j = i + 1; j <= n; j ++)
        {
            if (c[i].ansl and c[i].ansr) break;
            if (!c[i].ansl and c[j].l < c[i].l and c[j].r > c[i].l) c[i].ansl = c[j].id;
            if (!c[i].ansr and c[j].l < c[i].r and c[j].r > c[i].r)   c[i].ansr = c[j].id;
        }
    }

    sort(c + 1, c + 1 + n, cmp2);

    for (int i = 1; i <= n; i ++ )
    {
        cout << c[i].ansl << ' ' << c[i].ansr << endl;
    }

}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    solve();

    return 0;
}