基本思想是计算相邻的机器人每轮发生碰撞的时间，从小到大排列后依次发生碰撞
剩下的机器人相邻关系会改变，重新计算碰撞时间，重复上述步骤，直到没有碰撞发生
C++代码如下：
#include <bits/stdc++.h> // C++万能头文件
using namespace std;
using tri = tuple<double, int, int>; // 发生碰撞的时间和机器人编号
int main() {
int n, k;
cin >> n;
k = n; // 剩下机器人个数
int x[n + 1], v[n + 1]; // 初始位置和速度
for (int i = 1; i <= n; ++i) // 编号从1开始
cin >> x[i] >> v[i];
int crash[n + 1]; // 标记已碰撞的机器人
memset(crash, 0, sizeof(crash));
priority_queue<tri, vector<tri>, greater<tri>> pq; // 小根堆
while (k >= 2) { // 至少两个机器人才能相撞
int i = 1;
while (i < n && crash[i]) ++i;
while (i < n) {
int j = i + 1; // 计算与右侧机器人相撞时间
while (j <= n && crash[j]) ++j;
if (j > n) break;
long d = x[j] - x[i];
if (v[i] <= 0 && v[j] < v[i] // j撞上i
|| (v[i] > 0 && v[j] < v[i])) { // i撞上j
long delta_v = v[i] - v[j];
double t = d * 1.0 / delta_v;
pq.emplace(t, i, j);
}
i = j;
}
if (pq.empty()) break; // 没有相撞的机器人
while (!pq.empty()) {
auto t = pq.top();
pq.pop();
int ii = get<1>(t), jj = get<2>(t);
if (!crash[ii] && !crash[jj]) { // 都还在才能相撞
crash[ii] = crash[jj] = 1;
k -= 2;
}
}
}
cout << k << "\n";
for (int i = 1; i <= n; ++i) {
if (!crash[i])
cout << i << " ";
}
cout << "\n";
return 0;
}
已通过给出的测试用例，但需要更多用例测试是否正确，望采纳~
