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：复制

输出样例#1：复制

说明

思路：贪心。

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

int n;

struct nond{

    int h,l,r,id,ansl,ansr;

}v[];

int cmp(nond a,nond b){

    if(a.h==b.h)    return a.l<b.l;

    return a.h>b.h;

}

int cmp1(nond a,nond b){

    return a.id<b.id;

}

int main(){

    scanf("%d",&n);

    for(int i=;i<=n;i++){

        scanf("%d%d%d",&v[i].h,&v[i].l,&v[i].r);

        v[i].id=i;

    }

    sort(v+,v++n,cmp);

    for(int i=;i<=n;i++){

        for(int j=i+;j<=n;j++){

            if(v[i].ansl&&v[i].ansr)    break;

            if(!v[i].ansl&&v[j].l<v[i].l&&v[j].r>v[i].l)    v[i].ansl=v[j].id;

            if(!v[i].ansr&&v[j].l<v[i].r&&v[j].r>v[i].r)    v[i].ansr=v[j].id;

        }

    }

    sort(v+,v++n,cmp1);

    for(int i=;i<=n;i++)

        cout<<v[i].ansl<<" "<<v[i].ansr<<endl;

}

巴特西

洛谷 P1105 平台

P1105 平台

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章