题目：
出题人在\(x\)轴上放置了\(n\)个正在移动的炸弹，第iii个炸弹的初始位置为\(x[i]\)，速度为\(v[i]\)，当两颗炸弹相遇时会发生爆炸，导致这两颗炸弹消失。在经历了\(10^{100000}\)秒后，出题人想知道最后还剩下几颗炸弹，以及它们的编号。(数据保证不会有三个及以上的炸弹同时相遇)
分析：
由于炸弹运动时间可以看做无限长，所以所有有相对运动迹象的炸弹都会爆炸，我们可以将所有相邻的炸弹的相遇时间扔进优先队列（对于炸弹的3*3种情况讨论），用set维护下标删除炸弹即可。
实现：
#include using namespace std;#define rep(i, a, n) for(int i = a; i < n; i++)#define all(x) x.begin(), x.end()#define pb push_back#define ios ios::sync_with_stdio(false);cin.tie(0);#define debug(x) cout << x << endl;#define SZ(x) (int)x.size()typedef long long LL;typedef unsigned long long ULL;typedef pair PII;const double inf = 1e18;void read(int &x) {int s = 0, f = 1; char ch = getchar(); while(!isdigit(ch)) {f = (ch == '-' ? -1 : f); ch = getchar();} while(isdigit(ch)) {s = s * 10 + ch - '0'; ch = getchar();} x = s * f;}const int N = 100005;int n;int vis[N];struct node { int x, v, id; bool operator < (const node& aa) const { return x < aa.x; }} a[N];struct Node { //优先队列维护碰撞时间最短的两个炸弹 int u, v; double time; bool operator aa.time; }};priority_queue q;set s;double calc(int idx1, int idx2) //计算相邻的炸弹的碰撞时间{ double dis = abs(a[idx1].x - a[idx2].x) * 1.0; int v1 = a[idx1].v, v2 = a[idx2].v; if(v1 == v2) //都为0 或者速度相同 return inf; if(v1 == 0) { if(v2 0) return dis / abs(v1); else return inf; } if(v1 0) return inf; if(v1 > 0 && v2 < 0) return dis / (abs(v1) + abs(v2)); if(v1 < 0 && v2 abs(v1)) return dis / (abs(v2) - abs(v1)); else return inf; } if(v1 > 0 && v2 > 0) { if(abs(v1) > abs(v2)) return dis / (abs(v1) - abs(v2)); else return inf; } return inf;}signed main(){ cin >> n; for(int i = 0; i > a[i].x; a[i].id = i; } rep(i, 1, n + 1) cin >> a[i].v; sort(a + 1, a + n + 1); for(int i = 2; i <= n; i ++) q.push({i - 1, i, calc(i - 1, i)}); while(q.size()) { auto tmp = q.top(); q.pop(); if(tmp.time == inf) break; if(vis[tmp.u] || vis[tmp.v]) continue; vis[tmp.u] = 1; vis[tmp.v] = 1; int l, r; auto iter = s.find(tmp.u); l = *(--iter); iter ++; s.erase(iter); iter = s.find(tmp.v); r = *(++iter); iter --; s.erase(iter); if(l == 0 || r == n + 1) continue; q.push({l, r, calc(l, r)}); } vector res; for(int x : s) if(x != 0 && x != n + 1) res.pb(a[x].id); sort(all(res)); cout << SZ(res) << '\n'; for(int x : res) cout << x << '\n';}