題目：
? 出題人在\(x\)軸上放置了\(n\)個正在移動的炸彈，第iii個炸彈的初始位置為\(x[i]\)，速度為\(v[i]\)，當兩顆炸彈相遇時會發生爆炸，導致這兩顆炸彈消失，在經歷了\(10^{100000}\)秒后，出題人想知道最后還剩下幾顆炸彈，以及它們的編號，(資料保證不會有三個及以上的炸彈同時相遇)
分析：
? 由于炸彈運動時間可以看做無限長，所以所有有相對運動跡象的炸彈都會爆炸，我們可以將所有相鄰的炸彈的相遇時間扔進優先佇列（對于炸彈的3*3種情況討論），用set維護下標洗掉炸彈即可，
實作：
#include <bits/stdc++.h>
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<int, int> 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 < (const Node& aa) const {
return time > aa.time;
}
};
priority_queue<Node> q;
set<int> 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(v2);
else
return inf;
}
if(v2 == 0)
{
if(v1 > 0)
return dis / abs(v1);
else
return inf;
}
if(v1 < 0 && v2 > 0)
return inf;
if(v1 > 0 && v2 < 0)
return dis / (abs(v1) + abs(v2));
if(v1 < 0 && v2 < 0)
{
if(abs(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 <= n + 1; i ++)
s.insert(i);
rep(i, 1, n + 1)
{
cin >> 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<int> 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';
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/505497.html
標籤：其他