1 条题解
-
0
何老师 (root) LV 0 MOD @ 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