我要招人

去企业版

首页 > 试题广场 >

撞车

[编程题]撞车

热度指数：2658 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

一条单向单车道的道路上有 $n$ 辆车，第 $i$ 辆车位于 $x_i$ ，速度大小为 $v_i$ 。

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

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

输入描述:

第一行一个整数  ，表示车的数量。

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

数据保证  互不相同。

输出描述:

输出一行一个整数，表示需要移除车的数量。

示例1

输入

输出

示例2

输入

输出

算法知识视频讲解

丨阿伟丨

发表于 2025-08-28 14:25:07

题目链接撞车题目描述一条单向单车道的道路上有辆车，第辆车位于，速度大小为。为了避免碰撞，可以移除一些车辆。请求出至少需要移除几辆车，才能让剩下的车不发生碰撞。解题思路两辆车会发生碰撞的充要条件是：位于后方的车辆速度快于前方的车辆。换言之，要使任意两辆车和不发生碰撞，如果展开全文

BraveCoder

发表于 2025-09-23 10:57:27

import java.util.*; public class Main { static class Car { long x; // 使用long避免位置值过大导致溢出 int v; Car(long x, int v) { 展开全文

归虚梦演

发表于 2025-08-05 20:02:53

#include <bits/stdc++.h> using namespace std; #define int long long #define PII pair<int,int> #define endl '\n' #define INF 2e18 #define u 展开全文

自由的风0450

发表于 2025-12-12 12:55:43

#include <iostream> #include<vector> #include<algorithm> using namespace std; struct car{ int x,v; }; bool compare(const car&am 展开全文

ZYCwuque

发表于 2025-08-23 02:14:41

import java.util.ArrayList; import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { // TO 展开全文

腌萝卜干

发表于 2026-01-30 13:58:49

分析因为是单行道, 不发生碰撞的条件是并且那么只需要将车按照位置排序, 然后计算最长不下降子序列即可因为, 需要贪心 + 二分优化计算代码实现 #include <bits/stdc++.h> #define x first #define y second using na 展开全文

czw230

发表于 2025-08-23 17:36:46

import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public cl 展开全文

楼毅骞

发表于 2026-01-29 13:21:56

//要满足题设，我们需要让速度单调递增，不要求严格 //单向道，线性，位置需要升序排序,采用结构体. //对于速度，我们需要动态规划 //创建一个dp[i],对vi[i]>=dp.back()的尾插,对vi[i]<dp.back()的,upper_bound找到d里严格大于他的一个并替换展开全文

冷艳的西红柿刷牛客

发表于 2025-10-09 00:17:35

import java.util.Arrays; import java.util.Comparator; import java.util.Scanner; import java.util.function.Function; /** * @author supermejane * @da 展开全文