首页 > 代码库 > P1105 平台

P1105 平台

题目描述

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

输入输出格式

输入格式:

 

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

接下来N行每行3个整数 分别是平台的高度H[i],左端点的X坐标L[i],右端点的X坐标R[i].

其中,1<=N<=1000 0<=H,L,R<=20000。

 

输出格式:

 

输出共N行 每行2个数 分别是

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

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

 

输入输出样例

输入样例#1:
52 0 24 1 33 1 35 3 41 1 5
输出样例#1:
0 51 51 55 50 0

说明

技术分享

 

一个简单的模拟

有一个坑是同样高度的序号小的优先

 

代码

#include<bits/stdc++.h>using namespace std;#define ll long long int#define maxn 100000+15struct EDGE{    ll num,l,r,w,h;}edge[maxn],edge2[maxn];ll n,m,maxx,x,y,z;bool cmp(EDGE a,EDGE b){    if(a.h!=b.h) return a.h<b.h;    else return a.num>b.num;}int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++)    {        scanf("%d%d%d",&z,&x,&y);        edge[i].num=i;        edge[i].h=z;        edge[i].l=x;        edge[i].r=y;        edge2[i].num=i;        edge2[i].h=z;        edge2[i].l=x;        edge2[i].r=y;        maxx=max(maxx,y);    }    edge[0].h=0;    edge[0].l=-1;    edge[0].r=maxx+1;    sort(edge+1,edge+n+1,cmp);    for(int i=1;i<=n;i++)    {        for(int j=n;j>=0;j--)        {            if(edge[j].h<edge2[i].h)            {                if(edge[j].l<edge2[i].l&&edge[j].r>edge2[i].l)                {                    printf("%d ",edge[j].num);   break;                }            }        }        for(int j=n;j>=0;j--)        {            if(edge[j].h<edge2[i].h)            {                if(edge[j].l<edge2[i].r&&edge[j].r>edge2[i].r)                {                    printf("%d ",edge[j].num);     break;                 }            }        }        printf("\n");    }    return 0;}

 

P1105 平台