思路: 动态规划 + 二分查找

首先将所有车辆按位置升序排序，确保处理顺序正确。然后提取速度序列，目标是找到最长不下降子序列，代表可以保留的最大车辆数而不发生碰撞。使用动态规划和二分查找的方法高效计算最长不下降子序列。最后，最少需要移除的车辆数即为总车辆数减去最长不下降子序列大小，从而避免所有可能的碰撞。

代码

java

import java.util.*;

class Node {
    long x, v;

    Node(long x, long v) {
        this.x = x;
        this.v = v;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Node[] b = new Node[n];

        for (int i = 0; i < n; i++) {
            long x = sc.nextLong();
            long v = sc.nextLong();
            b[i] = new Node(x, v);
        }

        Arrays.sort(b, (a, b2) -> Long.compare(a.x, b2.x));

        long[] a = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            a[i] = b[i - 1].v;
        }

        long[] dp = new long[n + 1];
        dp[1] = a[1];
        int pos = 1;

        for (int i = 2; i <= n; i++) {
            if (a[i] >= dp[pos]) {
                pos++;
                dp[pos] = a[i];
            } else {
                int idx = Arrays.binarySearch(dp, 1, pos + 1, a[i]);
                if (idx < 0) idx = -idx - 1;
                dp[idx] = a[i];
            }
        }

        System.out.println(n - pos);
    }
}

python

import bisect

class Node:
    def __init__(self, x, v):
        self.x = x
        self.v = v

n = int(input())
b = []

for _ in range(n):
    x, v = map(int, input().split())
    b.append(Node(x, v))

b.sort(key=lambda node: node.x)

a = [0] * (n + 1)
for i in range(1, n + 1):
    a[i] = b[i - 1].v

dp = [0] * (n + 1)
dp[1] = a[1]
pos = 1

for i in range(2, n + 1):
    if a[i] >= dp[pos]:
        pos += 1
        dp[pos] = a[i]
    else:
        idx = bisect.bisect_left(dp, a[i], 1, pos + 1)
        dp[idx] = a[i]

print(n - pos)

cpp

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define N 100005
struct node{
	int x,v;
}b[N];
int a[N];
int dp[N];
bool cmp(node a,node b){
	return a.x<b.x;
}
int n;
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>b[i].x>>b[i].v;
	}
	sort(b+1,b+n+1,cmp);
	for(int i=1;i<=n;i++){
		a[i]=b[i].v;
	}
	int pos=1;
	dp[1]=a[1];
	
	for(int i=2;i<=n;i++)
	{
		if(a[i]>=dp[pos])
			dp[++pos]=a[i];
		else
			dp[lower_bound(dp+1,dp+pos+1,a[i])-dp]=a[i];
	}
	cout<<n-pos<<'\n';
	return 0;
}

OJ会员可以通过点击题目上方《已通过》查看其他通过代码来学习。

题目内容

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

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

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

输入描述

第一行一个整数 $n(1 ≤n≤ 10^5)$，表示车的数量。

接下来$n$ 行，每行两个整数 $x_i,v_i(|x_i|,|v_i|,|v_i|≤ 10^9)$，表示车的位置和速度的大小。

数据保证 $x_i$ 互不相同。

输出描述

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

样例1

输入

3
-1 -1
0 0
1 1

输出

0

说明

样例2

输入

3
-1 1
0 0
1 -1

输出

2

说明