首页 > 代码库 > 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 平台
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。