首页 > 试题广场 >

观赏风景

[编程题]观赏风景
  • 热度指数：686 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解

有 n 座摩天大楼等间距地排成了一排，你对从哪座摩天大楼的顶端欣赏风景这个问题很感兴趣。每一座摩天大楼都可以被抽象为一条在二维平面上的一条线段。你现在知道第 i 座大楼的高度为 hi ，对应在二维平面上就是(i , 0)到(i , hi)的一条线段。

你现在想到能看到最多楼顶的大楼去，从第 i 座大楼能看到第 j 座大楼当且仅当连接这两个楼顶的线段不与任何其他高楼对应的线段接触或相交。现在要请选择一座能看到最多其他楼顶的大楼。


输入描述:
每组测试用例仅包含一组数据，每组数据第一行为一个正整数 n (1 ≤ n ≤ 60) ， 接下来一行有 n 个整数 hi 表示第 i 座大楼的高度( 1 ≤ ai ≤ 1000000000)。


输出描述:
输出一个数，代表你最多能看到的其他楼顶数量。
 
对于样例，从第 3 座大楼楼顶可以看到其他所有楼顶。
示例1

输入

5 1 2 7 3 2

输出

4
算法知识视频讲解
开通博客

暂无题解

问题信息

C++工程师 声网 2020
来自：声网2020校招-通用...
上传者：小小
难度：
8条回答 2969浏览

热门推荐

通过挑战的用户

相关试题

观赏风景

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号