首页 > 试题广场 >

观赏风景

[编程题]观赏风景
  • 热度指数：717 时间限制：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
算法知识视频讲解
添加回答
一个不愿透露姓名的奋斗比头像 一个不愿透露姓名的奋斗比
这道题做的我头皮发麻，1.样例给了一行，然后我想破脑袋也不知道为啥是4 一直算的是5，又看了一遍发现第一个数不是楼高。2.看题的情景是高楼看风景，但是看约束条件，好像从下往上看楼顶也算。。。然后发现果然是这样，emm行吧，去外滩上东方明珠干嘛，站在地上看见楼顶也算呗。。。。
题目很简单就是斜率单项变化，python代码交的，这里写一下C++的代码

许愿声网大大私聊我免笔试 
#include<bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin>>n;
    vector<int> a(n,0);
    for (int i=0;i<n;i++){
        cin>>a[i];
    }
    //cout<<a.size()<<" "<<a[13]<<endl;
    int res = 0;
    for (int i=0;i<n;i++){
        int ress= 0;
        int l = i-1;
        double ll1 = 100000000000000;
        while (l>=0){
            double kk =double((a[i]-a[l]))/double((i-l));
            if (kk<ll1){
                ll1 = kk;

                ress ++;

            }
            l --;
        }
        //cout<<i<<" "<<ress<<endl;
        int r = i+1;
        double rr1 = 100000000000000;
        while(r<n){
            double kk = double((a[i]-a[r]))/double((r-i));
            if (kk<rr1){
                rr1 = kk;

                ress ++;
                }
            r ++;

        }
        //cout<<i<<" "<<ress<<endl;

        res = max(res,ress);
    }
    cout<<res;
}



编辑于 2020-08-20 14:28:29 回复(3)
小桥流水夜景美如画头像 小桥流水夜景美如画
用一个vector<int> a 记录所有楼，对于a[n]，n和n左边结点之间直线的斜率，满足升序规律；n和n右边结点之间的直线的斜率，也满足升序规律；当有结点直线的斜率不满足升序规律时，把这个点忽略；如果后面的结点依然满足升序，则能看见。
请各位大佬批评指正：
#include <iostream>
#include<vector>
using namespace std;
//
int Sort_func(vector<int> a, int n){
    int left = 0, right = 0;
    // 计算a[n]左边能看到的数量
    if(n==0 || n ==1)
        left = n;
    else{
        double x1 = double(a[n] - a[n-1]);
        for(int i = 1; i<=n-1; i++){
            if (x1 < (double(a[n] - a[n-i-1]) / (i + 1))){
                left++;
                x1 = double(a[n] - a[n-i-1]) / (i + 1);
            }
        }
    }

    // 计算a[n]右边能看到的数量
    if(n==a.size()-1)
        right = 0;
    else if(n ==a.size()-2)
        right = 1;
    else{
        double x2 = double(a[n]-a[n+1]);
        for(int i = 1; i<=a.size()-n-3; i++){
            if(x2 < (double(a[n]-a[n+i+1]) / (i+1))){
                right++;
                x2 = double(a[n]-a[n+i+1]) / (i+1);
            }
        }
    }
    return left + right;
}

int main()
{
    int n;
    vector<int> a(n, 0);
    while(cin>>n){
        int m;
        for(int i=0; i<n; i++){
            cin>>m;
            a[i] = m;
        }
        // 遍历每个结点的可见数量，求最大值
        int ans = 0;
        for(int i=0; i<n; i++){
            ans = max(ans, Sort_func(a, i));
        }
        cout<<ans<<endl;
    }
    return 0;
}
编辑于 2020-09-02 15:13:01 回复(1)
牛客240049944号头像 牛客240049944号
i能看到j，j也能看到i 
#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;
int main(){
    int n,m;
    cin >> n;
    vector<int> a(n);
    for(int i = 0;i < n;++i){
        cin >> a[i];
    }
    unordered_map<int,int> b;
    for(int i = 0;i < n-1;++i){
        double kk = a[i+1] - a[i] - 1;
        for(int j = i + 1;j < n;++j){
            double temp = (a[j] - a[i]) / (double)(j - i);
            if(temp > kk){
                kk = temp;
                b[i]++;
                b[j]++;
            }
        }
    }
    int res = 0;
    for(auto [i,j]:b){
        res = max(res,j);
    }
    cout << res << endl;
    return 0;
}



发表于 2022-07-12 15:00:08 回复(0)
ssrrss头像 ssrrss
模拟的时候需要仔细的考虑遮挡问题。以下是没有品位的解法。 
#include<iostream>
#include <algorithm>
using namespace std;

int solve(int s,int n,const double* v){
    int sum=0;
    double max_k=*max_element(v,v+ n)+1;
    double min_k=*min_element(v,v+ n)-*max_element(v,v+ n)-1;
    double k=max_k;
    for(int i=s-1;i>=0;i--){
        if ( (v[s]-v[i])/(s-i)<k ) {
            k=(v[s]-v[i])/(s-i);
            sum++;
        }
    }
    k=min_k;
    for(int i=s+1;i<n;i++){
        if ( (v[s]-v[i])/(s-i)>k ) {
            k=(v[s]-v[i])/(s-i);
            sum++;
        }
    }
    return sum;
}

int main()
{
    double v[1000];
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    int m[1000];
    for (int i=0;i<n;i++){
        m[i]=solve(i,n,v);
    }
    int max=-1;
    for (int i=0;i<n;i++){
        if (max<m[i])max=m[i];
    }
    cout<<max<<endl;
    return 0;
}


发表于 2020-12-28 21:49:19 回复(0)
牛客264793651号头像 牛客264793651号
第一次k2（当前斜率最值）的刷新条件错了,这是改过后的正确的代码
#include<cstdio>
int h[60];
int main()
{
    int i1, i2, n, res1, res2;
    double k1, k2;
    scanf("%d", &n);
    for (i1 = 0; i1 < n; ++i1)
    {
        scanf("%d", h + i1);
    }
    if (n <= 3)
        printf("%d", n - 1);
    res2 = 0;
    for (i1 = 0; i1 < n; ++i1)
    {
        if (i1 - 1 >= 0)
        {
            if (i1 + 1 < n)
                res1 = 2;
            else
                res1 = 1;
        }
        else
            res1 = 1;
        i2 = i1-2;
        k2 = (double)(h[i1] - h[i1 - 1]);
        while (i2 >= 0)
        {
            k1 = (double)(h[i2] - h[i1]) / (i2 - i1);
            if (k1 < k2)
            {
                res1++;
                k2 = k1;
            }
            --i2;
        }
        i2 = i1 + 2;
        k2 = (double)(h[i1 + 1] - h[i1]);
        while (i2 < n)
        {
            k1 = (double)(h[i2] - h[i1]) / (i2 - i1);
            if (k1 > k2)
            {
                res1++;
                k2 = k1;
            }
            ++i2;
        }
        if (res1 > res2)
            res2 = res1;
    }
    printf("%d\n", res2);
    return 0;
}
发表于 2020-12-04 21:41:47 回复(0)
ddqh头像 ddqh 
#include<iostream>
#include<vector>
using namespace std;

class Solution{
 public:
    int maxRoof(vector<int> vec){
        int ret=0;
        if(vec.size()<=1) return 0;
        for(int i=1;i<=vec[0];i++){
            int tmpsize=0;
            for(int j=1;j<=vec[0];j++){
                if(j==i) continue;
                int ii=min(i,j);
                int jj=max(i,j);
                float k=float(vec[jj]-vec[ii])/(jj-ii);// 斜率
                float b=vec[jj]-k*jj;//偏置
                ii++;
                bool flag=true;
                while(ii<jj){
                    if(float(vec[ii]>=(k*ii+b)))
                    {
                        flag=false;
                        break;
                    }
                    ii++;
                    //xie'l
                }
                if(flag) tmpsize++;
                // i  -  j 区间内都满足
            }
            ret=max(ret,tmpsize);
        } 
        
        return ret;
    }
    
};
int main(){
    int n;
    cin >> n;
    vector<int> vec(n+1, 0);
    vec[0]=n;
    for (int i = 1; i <= n; i++) {
        cin >> vec[i];
    }
    
    Solution sol;
    int ret=sol.maxRoof(vec);
    cout<<ret;
    return 0;
}

发表于 2020-11-28 15:23:57 回复(0)
C/C++
牛客81917758号头像 牛客81917758号 
#include<iostream>
using namespace std;
int n;
int a[60];
int cou = 0;
int Slop() {
	int lcou = 0;
	for (int i = 0; i < n; i++) {
        int rcou = 0;
		int Ji = i - 1;
		double ss = 1000000000000;
		while (Ji >= 0) {
			double sl = double(a[i] - a[Ji]) / (i - Ji);
			if (sl < ss) {
				ss = sl;
				rcou++;
            }
			Ji--;
		}
		Ji = i + 1;
		ss = -100000000000;
		while (Ji < n) {
			double sl = double(a[i] - a[Ji]) / (i - Ji);
			if (sl > ss) {
				ss = sl;
				rcou++;
			}
			Ji++;
		}
		if (lcou<rcou) lcou = rcou;
}
	cout << lcou;
	return 0;
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
    }
	Slop();
	return 0;
}

从i开始把楼分成左右，计算斜率，往左去斜率逐渐变小，往右斜率逐渐变大，如果违反了渐变的规则，把这栋楼后面的楼忽略，直到出现一栋楼符合斜率渐变规则然后继续增加可以看到的楼栋，把左右两边可以看到的楼栋加起来就可以了。不过我有个问题，我和第一个回答者代码很像，但他第二个while里判定斜率是逐渐变小才增加，我是判定逐渐变大才增加，但是........为什么代码都通过了编译，想了很久没想明白。

编辑于 2020-10-31 21:57:13 回复(0)
听说不改名不中奖头像 听说不改名不中奖
C++写法  判断两线段有没有相交  一般可以用叉积来进行判断 。 
定义结构体是double类型的  一定要处理精度
定义结构体得是long long 类型的    a*b<=0 时候要注意a*b会炸longlong 要分类讨论 
#include<bits/stdc++.h>
using namespace std;
struct Point{
    long long x,y;
    Point(){ x=0,y=0; }
    Point(long long _x,long long _y):x(_x),y(_y){}
    long long operator ^(const Point &b)const{     return x*b.y-y*b.x;}//叉积
    Point operator -(const Point &b)const {     return Point(x-b.x,y-b.y);}
};
const int maxn=1e5+10;
long long a[maxn];
int num[maxn];
int32_t main(){
    int n; cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            Point aa;  aa.x=i; aa.y=a[i];
            Point bb;  bb.x=j; bb.y=a[j];
            bool f=1;
            for(int x=i+1;x<j;x++){
                Point cc; cc.x=x; cc.y=0;
                Point dd; dd.x=x; dd.y=a[x];
                Point aaa=cc-aa;
                Point bbb=cc-bb;
                Point ccc=dd-aa;
                Point ddd=dd-bb;
                if(       (aaa^bbb) == 0 || (ccc^ddd)==0)       { f=0; }
                else if(  (aaa^bbb) < 0 && (ccc^ddd) > 0)  { f=0; }
                else if(  (aaa^bbb) > 0 && (ccc^ddd) < 0 ) { f=0; }
            }
            if(f){  num[i]++; num[j]++;  }
        }
    } int t=0;
    for(int i=1;i<=n;i++) t=max(t,num[i]);
    cout<<t<<endl;
}


发表于 2020-09-16 16:42:06 回复(0)
提交观点

问题信息

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

热门推荐

通过挑战的用户

相关试题

观赏风景

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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