Question

c++编程题，求大神解答。

急急急急急急急急！！！！！！！！！！！！

Answer 1

基本思想是计算相邻的机器人每轮发生碰撞的时间，从小到大排列后依次发生碰撞

剩下的机器人相邻关系会改变，重新计算碰撞时间，重复上述步骤，直到没有碰撞发生

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;

}

已通过给出的测试用例，但需要更多用例测试是否正确，望采纳~