每个城市建设规划在哪个网站,网站开发流程进度规划,做网络歌手的网站,搬家公司网站建设价格题目描述
轮廓线 • 每一个建筑物用一个三元组表示(L, H, R), 表示左边界, 高度和右边界。 • 轮廓线用X, Y, X, Y…这样的交替式表示。 • 右图的轮廓线为: (1, 11, 3, 13, 9, 0, 12, 7, 16,3, 19, 18, 22, 3, 23, 13, 29, 0) 。 • 给N个建筑#xff0c;求…题目描述
轮廓线 • 每一个建筑物用一个三元组表示(L, H, R), 表示左边界, 高度和右边界。 • 轮廓线用X, Y, X, Y…这样的交替式表示。 • 右图的轮廓线为: (1, 11, 3, 13, 9, 0, 12, 7, 16,3, 19, 18, 22, 3, 23, 13, 29, 0) 。 • 给N个建筑求轮廓线。 输入输出格式
输入格式 输入数据共 n1 行。 第一行一个整数n。 n 10^4 第 2 至 n1 行每行有3个整数L、H、R分别表示一个建筑物左边界、高度、右边界数据均小于 2^30 。
输出格式 输出数据一行建筑物的轮廓线表示为x y x y x y ………… 注整数与整数之间用一个空格间隔
输入输出样例
输入样例#1
8 1 11 5 2 6 8 3 13 9 12 7 16 15 3 26 19 18 22 23 13 29 24 5 28
输出样例#1
1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0
提示信息 数据范围 30%数据n 10^2。 50%数据n 10^3。 100%数据n 10^4。
算法分析
题目的意思有点难看懂但通过观察样例数据可以发现对于任意坐标设为a[i].
则a[i]a[i-1] 活a[i]a[i-1]时输出a[i]与i 那么这就只是一个离散化的little problem
上代码
#includebits/stdc.h
using namespace std;
struct D{int w1;//矩形左边界坐标int w2;//矩形右边界坐标int h;//矩形高
}read[10001];
int sor[10001];
int a[10001],maxn,sn,n;//a[i]为坐标为i的最大高度maxn为离散化后最大坐标sn位坐标个数
mapint,int m;//数据过小可以用map
int rever[10001];
int main()
{cinn;for(int i1;in;i){cinread[i].w1read[i].hread[i].w2;sor[sn]read[i].w1;sor[sn]read[i].w2; }int cnt0;sort(sor1,sorsn1);for(int i1;isn;i){if(sor[i]!sor[i-1]) {m[sor[i]]cnt;rever[cnt]sor[i];}}//离散化for(int i1;in;i){read[i].w1m[read[i].w1];read[i].w2m[read[i].w2];maxnmax(maxn,read[i].w2);for(int jread[i].w11;jread[i].w2;j) a[j]max(a[j],read[i].h);//寻找a[i]}for(int i1;imaxn1;i){if(a[i]a[i-1]||a[i]a[i-1]){coutrever[i-1] a[i] ;}}return 0;
}
