#P2111. 第2题-撞车
-
1000ms
Tried: 151
Accepted: 13
Difficulty: 5
所属公司 :
京东
时间 :2024年9月21日
第2题-撞车
思路: 动态规划 + 二分查找
首先将所有车辆按位置升序排序,确保处理顺序正确。然后提取速度序列,目标是找到最长不下降子序列,代表可以保留的最大车辆数而不发生碰撞。使用动态规划和二分查找的方法高效计算最长不下降子序列。最后,最少需要移除的车辆数即为总车辆数减去最长不下降子序列大小,从而避免所有可能的碰撞。
代码
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辆车位于 xi;,速度大小为 vi 。
显然,如果车辆保持此速度行驶下去,在大多数情况下都会发生碰撞。
现在小红想知道,至少需要移除几辆车,才能让这些车不发生碰撞?
输入描述
第一行一个整数 n(1≤n≤105),表示车的数量。
接下来n 行,每行两个整数 xi,vi(∣xi∣,∣vi∣,∣vi∣≤109),表示车的位置和速度的大小。
数据保证 xi 互不相同。
输出描述
输出一行一个整数,表示需要移除车的数量。
样例1
输入
3
-1 -1
0 0
1 1
输出
0
说明
样例2
输入
3
-1 1
0 0
1 -1
输出
2
说明