105 - The Skyline Problem
Time limit: 3.000 seconds
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=41
这题有个很巧的思路:离散化。
什么意思呢?既然每栋大楼的高和左右边界都是整数,那么不妨把线段用一个个整点表示。既然最后只求一个轮廓,那么对每个横坐标,就记录纵坐标(高度)最大的点。最后从左到右扫描一遍,当高度发生变化时就输出。
完整代码:
/*0.039s*/
#include<bits/stdc++.h>
using namespace std;
const int maxn = 10005;
int hi[maxn];
int main()
{
int i, l, h, r, maxr = 0;
while (~scanf("%d%d%d", &l, &h, &r))
{
for (i = l; i < r; i++)
hi[i] = max(hi[i], h); ///注意右端点处不记录高度
maxr = max(maxr, r);
}
for (i = 1; i < maxr; ++i)
if (hi[i] != hi[i - 1])
printf("%d %d ", i, hi[i]);
printf("%d 0\n", maxr);
return 0;
}
分享到:
相关推荐
The Skyline Operator : Stephan Borzsonyi, Donald Kossmann, Konrad Stocker 论文
title = {Proceedings of the 17th International Conference on Data Engineering, April 2-6, 2001, Heidelberg, Germany}, publisher = {IEEE Computer Society}, year = {2001}, isbn = {0-7695-1001-9}, ...
经典的c语言教材,c语言发明者编写的教材,c语言学习者必备的
skyline项目开发介绍 skyline项目开发介绍 skyline项目开发介绍
建模软件skyline,配合之前上传的帮助使用
skyline-edge-69.apk is the final version that was released. Continuation of the project is being done under the name Strato. Strato Discord Server Link: https://discord.gg/YhpdhVBmXX
VB skyline 简单的代码 试用初学者
skyline 开发注意要点skyline 开发注意要点skyline 开发注意要点skyline 开发注意要点
SKYLINE 6.5
Skyline最新产品SkylineGLobe v7.0产品技术白皮书,详细介绍了SkylineGlobe v7.0产品概况、新特性、最新技术等内容。
skyline 教程 Demo API 开发教程
SkyLine之js代码demo
skyline; skyline 7.0; SLTerraExplorerPro; TerraExplorer; SmartEarth
开发文档,适合做skyline二次开发的文档
本文包括两方面的内容,一方面是介绍Skyline开发帮助文档,另一方面是根据帮助文档编写一个Skyline的例程
SkylineGlobe产品架构 SkylineGlobe产品架构 SkylineGlobe产品架构
skyline,实景三维模型查看工具,TerraExplorer,倾斜摄影测量,业类最先进的三维基础平台,官方最新版本
Skyline_Analysis_CreateFlood 示例
Skyline系列中的TerraExplorerPro官方中文教程!
Skyline最新证书license 支持6.1