题解：P17031 [NWERC 2020] 飞行碰撞 / Flight Collision

· · 题解

一道看起来容易实际实现并不容易的模拟题，刚开始我一瞪眼就去用了排序模拟做，遂挂之，连样例都没过。后来我用双向链表和优先队列一模拟就做出来了。

先说说我调半天调出正解发现的一个重要的性质。

假设有俩无人机 i,j，它们在某一时刻撞了，但是如果它们之间有个无人机 k(i<k<j) 的话，它们俩就撞不了，因为当中有个无人机 k 挡着，要么 i 和 k 撞了，要么 k 和 j 撞了。

从这个咱就能发现了，只有相邻的无人机，它们相撞才可能是最早发生的相撞。

有了这个性质，咱就能去做了。

直接看步骤吧：

  1. 才开始时，把所有相邻无人机对 (i,i+1) 当成候选的事件，如果它们要碰撞的话，就去计算它们的碰撞时间。
  2. 用小根堆按照碰撞的时间去取出最早的碰撞事件。
  3. 取出后，去查查一下双方活着没有，且双方相不相邻。如果满足的话，就代表它们发生了碰撞，直接把它们标记为坠毁，且将它们从链表里删了。（这儿我才开始时忘了判相邻了，结果直接写炸了，卡了我半小时寻不着问题在哪。大家一定要记得去判断。）
  4. 删了后，它们的前头一个和后头一个成了新的相邻对，计算这对的时间并入堆。
  5. 一直重复这样等到堆空。

碰撞时间的计算也就是个小学学的追及问题，相信大家都会，那我也懒得去说了，我这里也是直接给个结论：

  1. 如果 v_i>v_j，那么它们会相遇，时间 t=\frac{x_j-x_i}{v_i-v_j}。
  2. 如果 v_i \le v_j，那么它们不会相遇。

::::success[AC Code]

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n;
vector<ll> x(1),v(1);
struct node
{
    ll num,den;
    int i,j;
};
//小根堆
struct cmp
{
    bool operator()(node a,node b) const
    {
        ll l=a.num*b.den;
        ll r=b.num*a.den; //直接交叉乘法算出来乘积，这也是小学学的，也不多说了
        if(l!=r) return l>r;
        return a.i>b.i;
    }
};
priority_queue<node,vector<node>,cmp> pq;

//入堆函数
void add(int a,int b)
{
    if(a==0||b==0) return;
    if(v[a]>v[b])
    {
        ll num=x[b]-x[a];
        ll den=v[a]-v[b];
        pq.push({num,den,a,b});
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n;
    x.resize(n+2),v.resize(n+2);
    for(int i=1;i<=n;++i) cin>>x[i]>>v[i];
    vector<int> pr(n+2),nx(n+2); //双向链表
    vector<bool> alive(n+2,1);
    for(int i=1;i<=n;++i)
    {
        pr[i]=i-1;
        nx[i]=i+1;
    }
    pr[1]=0;
    nx[n]=0;
    for(int i=1;i<n;i++) add(i,i+1);

    //碰撞过程
    while(!pq.empty())
    {
        node e=pq.top();
        pq.pop();
        int a=e.i,b=e.j; //这是第二步
        if(!alive[a]||!alive[b]) continue;
        if(nx[a]!=b) continue; //一定要记住这，要判相邻
        alive[a]=alive[b]=false;//这是第三步

        int L=pr[a],R=nx[b];
        if(L) nx[L]=R;
        if(R) pr[R]=L;
        add(L,R); //这是第四步
    }
    vector<int> ans;//记录永远不会坠毁的无人机
    for(int i=1;i<=n;++i)
    {
      if(alive[i]) ans.push_back(i);
    }
    cout<<ans.size()<<endl;//数量
    for(size_t i=0;i<ans.size();++i)
    {
        cout<<ans[i]<<" ";//编号
    }
    return 0;
}

::::