当前位置: 首页 > news >正文

京东-第2题-撞车

Powered by:NEFU AB-IN

Link

文章目录

  • 京东-第2题-撞车
    • 题意
    • 思路
    • 代码

京东-第2题-撞车

题意

一条单向单车道的道路上有n辆车,第i辆车位于 xi;,速度大小为 vi。
显然,如果车辆保持此速度行驶下去,在大多数情况下都会发生碰撞。
现在小塔想知道,至少需要移除几辆车,才能让这些车不发生碰撞

思路

将所有车辆按位置升序排序,提取速度,找最长递增子序列(LIS)即可。最少需要移除的车辆数即为总车辆数减去LIS长度。

代码

n, = IO.read()
cars = []
for _ in range(n):xi, vi = IO.read()cars.append((xi, vi))cars.sort(key=lambda x: x[0])speeds = [vi for xi, vi in cars]LIS = []
for speed in speeds:pos = bisect.bisect_left(LIS, speed)if pos == len(LIS):LIS.append(speed)else:LIS[pos] = speedmin_remove = n - len(LIS)
print(min_remove)
http://www.lryc.cn/news/443118.html

相关文章:

  • Vue3流程图插件-Vue Flow
  • 初始网络编程(下)
  • java计算机毕设课设—土地档案管理系统(附源码、文章、相关截图、部署视频)
  • 第4步CentOS配置SSH服务用SSH终端XShell等连接方便文件上传或其它操作
  • Spring:统一结果私有属性造成的前端无法访问异常报错问题
  • thinkphp 做分布式服务+读写分离+分库分表(分区)(后续接着写)
  • webpack的使用
  • MATLAB智能优化算法-学习笔记(3)——大规模邻域搜索算法求解旅行商问题【过程+代码】
  • 货币单位换算 - 华为OD统一考试(E卷)
  • 95、k8s之rancher可视化
  • 简单生活的快乐
  • 【JAVA开源】基于Vue和SpringBoot的在线文档管理系统
  • 大数据新视界 --大数据大厂之数据驱动决策:如何利用大数据提升企业竞争力
  • 【Linux】生产者消费者模型:基于阻塞队列,使用互斥锁和条件变量维护互斥与同步关系
  • 多层感知机paddle
  • linux-网络管理-网络服务管理 17 / 100
  • Docker上安装mysql
  • 【秋招笔试-支持在线评测】8.28华为秋招(已改编)-三语言题解
  • 基于python上门维修预约服务数据分析系统
  • React基础教程(10):React Hooks
  • JVM 调优篇9 调优案例6- cpu使用过载解决办法【超赞】
  • Spring8-事务
  • 在Python中,类是用于定义对象的蓝图或模板,而对象则是根据类创建的具体实例
  • 【小波去噪】【matlab】基于小波分析的一维信号滤波(对照组:中值滤波、均值滤波、高斯滤波)
  • CentOS 7官方源停服,配置本机光盘yum源
  • 2024年汉字小达人区级自由报名备考冲刺:2024官方模拟题练一练(续)
  • 实战Redis与MySQL双写一致性的缓存模式
  • KVM环境下制作ubuntu qcow2格式镜像
  • 基于SpringBoot+Vue的高校竞赛管理系统
  • PHP发邮件教程:配置SMTP服务器发送邮件?