描述 n辆车正在一条宽度只能容纳一辆车的隧道里疾速行进着,当速度快的车辆i追上速度慢的车辆j时,i的车速就必须降成和j一样的车速,此时我们将i和j看成一个小队。现在给定初始时刻每辆车的位置和速度,请问在经过时间t之后,n辆车会分成多少个小队。 输入 输入第1行两个整数n和t,如题意描述。 接下来一共输入n行,每行两个整数pi和si,分别表示第i辆车的位置和速度。 输入数据保证pi是严格升序的。 输出 输出一行一个整数,表示最终分成的队数 输入样例 1 5 3 0 1 1 2 2 3 3 2 6 1 输出样例 1 3 输入样例 2 20 278 23 11 44 191 72 238 83 104 143 346 174 248 178 293 225 73 227 12 236 223 238 33 240 96 271 77 281 241 304 59 333 221 363 384 366 80 379 399 395 157 输出样例 2 6 提示 1<=n<=100,000 1<=si,t<=1,000,000,000 0<=pi<=1,000,000,000 c++代码,不要解释
时间: 2024-04-09 11:28:25 浏览: 10
```cpp
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, t;
cin >> n >> t;
vector<pair<int, int>> cars(n);
for (int i = 0; i < n; i++) {
cin >> cars[i].first >> cars[i].second;
}
int count = 1; // 初始队数为1
int maxSpeed = cars[n-1].second; // 最后一辆车的速度
for (int i = n-2; i >= 0; i--) {
int targetSpeed = min(maxSpeed, cars[i].second); // 目标速度为当前车辆和最后一辆车速度的较小值
int distance = cars[i+1].first - cars[i].first; // 当前车辆到下一辆车的距离
int timeNeeded = distance * targetSpeed; // 到达下一辆车需要的时间
if (timeNeeded > t) { // 如果时间超过t,则需要分队
count++;
maxSpeed = cars[i].second; // 更新最后一辆车的速度
} else { // 否则继续向前推进
t -= timeNeeded;
maxSpeed = max(maxSpeed, cars[i].second); // 更新最后一辆车的速度
}
}
cout << count << endl;
return 0;
}
```