首页 > 试题广场 >

撞车

[编程题]撞车
  • 热度指数：1111 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
一条单向单车道的道路上有 n 辆车，第 i 辆车位于 x_i ，速度大小为 v_i 。

显然，如果车辆保持此速度行驶下去，在大多数情况下都会发生碰撞。

现在牛牛想知道，至少需要移除几辆车，才能让这些车不发生碰撞？

输入描述:
第一行一个整数  ，表示车的数量。

接下来 n 行，每行两个整数  ，表示车的位置和速度的大小。

数据保证 x_i 互不相同。


输出描述:
输出一行一个整数，表示需要移除车的数量。
示例1

输入

3
-1 -1
0 0
1 1

输出

0
示例2

输入

3
-1 1
0 0
1 -1

输出

2
算法知识视频讲解
查看答案及解析
添加回答
骆亮头像 骆亮
res=n-最长不严格上升子序列的长度
发表于 2025-07-26 00:32:59 回复(0)
提交观点

问题信息

动态规划 京东 排序
来自：华为机试编程模拟题8
难度：
1条回答 257浏览

热门推荐

相关试题

撞车

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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