题解

1 条题解

  • 0
    @ 2019-10-18 09:54:46

    1、算法分析
      设 P[i].a ,P[i].b 表示第i个山峰底边在x轴上的左右端点坐标,山峰是一个等腰直角三角形,(x,y)其直角点的坐标,则P[i].a=x-y,P[i].b=x+y。

      分析不难知道,当P[i].a>=P[j].a && P[i].b<=P[j].b,则山峰i被山峰j遮挡,由此统计能看见的山峰数算法如下:

      int Ans=n;
      for(int i=1;i<=n;i++)
         for(int j=i+1;j<=n;j++)
            if(P[i].a>=P[i].b && P[i].b<=P[j].b) Ans--;
    

      时间复杂度为 \(O(n^2)\)。

    2、优化算法:

      以左端点 P[i].b 进行关键字排序,即保证形成一个左端点依次变大,当左端点相同时,按P[i].b排序。O(n)遍历,维护一个序列最小左端点和最大右端点,统计答案即可。更详细地说,左到右依次扫描每个山峰,因为左端点由小到大排好序,用R记录当前能看到的山峰的右端点,对于下一个山峰i,如果P[i].b>R,则i一定不被遮挡。

      int Ans=1,B=p[1].b;
      for(int i=2;i<=n;i++)
        if(p[i].b>B) Ans++,B=p[i].b;
    
  • 1

信息

ID
1330
难度
4
分类
其他 | 排序模拟 点击显示
标签
递交数
0
已通过
0
通过率
?
被复制
1
上传者