【USACO 2019 January Silver】Mountain View题解
View 2019 题解 USACO
2023-09-14 08:57:17 时间
题目:
题目描述
从农场里奶牛Bessie的牧草地向远端眺望,可以看到巍峨壮丽的山脉绵延在地平线上。山脉里由N座山峰(1≤N≤10^5)。如果我们把Bessie的视野想象成xy平面,那么每座山峰都是一个底边在x轴上的三角形。山峰的两腰均与底边成45度角,所以山峰的峰顶是一个直角。于是山峰i可以由它的峰顶坐标(xi,yi)精确描述。没有两座山峰有完全相同的峰顶坐标。
Bessie尝试数清所有的山峰,然而由于它们几乎是相同的颜色,所以如果一座山峰的峰顶在另一座山峰的三角形区域的边界上或是内部,她就无法看清。
请求出Bessie能够看见的不同的山峰的峰顶的数量,也就是山峰的数量。
输入
输入的第一行包含N。以下N行每行包含xi(0≤xi≤109)和yi(1≤yi≤109),描述一座山峰的峰顶的坐标。
输出
输出Bessie能够分辨出的山峰的数量。
样例输入
3
4 6
7 2
2 5
样例输出
2
提示
在这个例子中,Bessie能够看见第一座和最后一座山峰。第二座山峰被第一座山峰掩盖了。
思路:
这可能类似以前的 一道题,那里我用的是STL模板,其实也能用堆做,但这都是优化,而这次这道题没法优化,可能数据太水,O(n^2)竟然过了。
我的方法是先以高度排序(降序),然后依次遍历一遍,如果没被前面的山覆盖,那就ans++。
可能有人会问,为什么要排序呢?我们可以想一想,高的山一定不可能被小的山覆盖,所以从高往低,可以算是一种优化吧?
可能又有人会问,如何判断它是否被前面的山覆盖呢?很简单,遍历比它高的山且那座山没被覆盖,如果y1-abs(x-x1)>y,那么x,y这座山就被覆盖了。
相关文章
- headless CMS_model view controller
- Android艺术开发探索学习 之 测量view的宽高 以及 动态设置View的位置
- listview加载性能优化之view的复用
- Android 自定义View 之 圆环进度条
- ORA-23435: cannot create an updatable ROWID materialized view with LOB columns ORACLE 报错 故障修复 远程处理
- MySQL Error number: MY-011640; Symbol: ER_GRP_RPL_TIMEOUT_ON_VIEW_AFTER_JOINING_GRP; SQLSTATE: HY000 报错 故障修复 远程处理
- ORA-12031: cannot use primary key columns from materialized view log on “string”.”string” ORACLE 报错 故障修复 远程处理
- MySQL Error number: MY-013753; Symbol: ER_GRP_RPL_VIEW_CHANGE_UUID_DIFF_FROM_GRP; SQLSTATE: HY000 报错 故障修复 远程处理
- Oracle 视图 DBA_ANALYTIC_VIEW_DIMS_AE 官方解释,作用,如何使用详细说明
- Oracle 视图 DBA_ANALYTIC_VIEW_HIER_CLS_AE 官方解释,作用,如何使用详细说明
- Oracle 视图 DBA_ANALYTIC_VIEW_LEVEL_CLASS 官方解释,作用,如何使用详细说明
- Oracle 视图 USER_ANALYTIC_VIEW_CALC_MEAS 官方解释,作用,如何使用详细说明
- Oracle 视图 USER_ANALYTIC_VIEW_HIERS 官方解释,作用,如何使用详细说明
- MySQL Status Mysqlx_crud_create_view 数据库状态作用意思及如何正确
- 如何从维护视图(Maintenace view)中取数据-[VIEW_GET_DATA]详解编程语言
- abap中VIEW_MAINTENANCE_CALL的用法详解编程语言
- Linux 中的 View 指令:深入理解(linux的view指令)
- 掌握Linux之道:深入学习View命令(linux命令view)
- Linux中View命令:简单而强大的文件查看方式(linux中view命令)
- 25 Ways to View Your Linux Configuration Information(linux配置信息查看)
- 如何修改Oracle数据库中的View(oracle修改view)
- Daydream View VR头盔将于11月10日发售,都有这些可玩的