题解：P10195 [USACO24FEB] Quantum Moochanics G

· · 题解

题意

有偶数个粒子，按照正反正反正反……的顺序排下去。第 i 个粒子的位置在 p[i]，速度为 s[i]。粒子的初始方向由其粒子性质决定，正粒子初始方向向右，反粒子初始方向向左。当 Bessie 看向这些粒子的时候，它们的方向会被改变。Bessie 会在实验开始后的第 1 秒，第 3 秒，第 6 秒……看向这些粒子。

综上所述，一个正粒子的运动轨迹大致如下（反粒子方向相反）：

思路

首先，我们观察发现。每一次发生湮灭的两个粒子在此之前一定是相邻的。

反证法，如果正粒子和反粒子之间还隔着粒子，那么中间一定既有正粒子也有反粒子，而且外正粒子与内反粒子相邻，内正粒子与外反粒子相邻，就会先发生湮灭。不存在能让内正反粒子湮灭前外正反粒子湮灭的情况。

所以我们很快就可以想到一个方法：先遍历所有相邻的粒子，查找第一对要湮灭的，使它们湮灭，然后使他们左右两边的粒子互相标记为相邻的。

那么，如何标记相邻状态呢？我们可以先定义两个数组 pre[] 和 nxt[] ，标记粒子的前后驱。当我们使两个粒子湮灭时，就让前粒子的前驱将后驱标记为后粒子的后驱，让后粒子的后驱把前驱标记为前粒子的前驱。

对的，就是数组模拟链表！

那么，如何计算哪一对粒子要先湮灭呢？

我们思考只有两个粒子的情况：

首先，如果正粒子在左侧，反粒子在右侧，设 k=\frac{t+1}{2}，此处的 t 是观察的次数。

那么每一个 t%2==1 时候，正粒子 i 的位置距离原来的点，向右偏移了 k 个 s[i]。同理，反粒子 j 向左偏移 k 个 s[j]。

当粒子相遇时，有：

p_i+ks_i \ge p_j-ks_j

化简得：

k \ge \frac{p_j-p_i}{s_i+s_j}

因为是大于等于，所以向上取整。

左边是反粒子，右边是正粒子的计算一模一样。只是 k=\frac{t}{2}。

由于正粒子编号为奇数，反粒子编号为偶数，所以粒子 x、y 相遇时间的计算就可以写出一个简洁的式子：

int ceil(int x,int y){
    return x/y+bool(x%y);
}

int ct(int x,int y){
    int k=ceil(p[y]-p[x],s[x]+s[y]);
    return 2*k-x%2;
}

但是如果直接遍历所有相邻的粒子显然会超时。那么如何优化这个过程呢？

我们可以使用优先队列。优先队列对于队列中的元素，按照从大到小的顺序编排。尽管我们想要的是相遇时间最小的那一对粒子，我们也可以通过取反来使得排序生效。由于 pair 的比较是按照第一个元素，所以我们套两层 pair，外面的 pair 把时间的相反数存在第一位用来排序，第二位再放一个 pair 存相邻的粒子。

但现在我们又遇到了一个问题。比如有这样一段正反粒子：

+1 -1 +2 -2

那在我们初始化的时候，我们要比较所有相邻的粒子，所以我们的优先队列里面存了 3 对粒子：

+1 -1
-1 +2
+2 -2

假设 -1 与 +2 最先湮灭，那么我们的粒子和队列情况会变成这样：

+1 -2
+1 -1
+2 -2
+1 -2 //新加的

可以看到，尽管 -1 和 +2 已经湮灭，但是队列中仍然保留这与它们有关的点对。如何将这些点对去除呢？

很简单，我们可以不去除它们，当它们被我们出队的时候，我们再看看之前它们是否出过队。如果出过队，但我们再 continue。

代码

#include<iostream>
#include<queue>
#define int long long
using namespace std;
const int N=2e5+5;

int p[N],s[N],a[N],pre[N],nxt[N];
//位置，速度，答案（存点是哪一次观察时湮灭的），前驱，后继 

void init(int n){
    for(int i=0;i<N;i++)
        a[i]=0;
//多测要记得清空答案数组，因为这里的答案数组兼职vis的功能 
    for(int i=1;i<=n;i++){//初始化前驱后继 
        pre[i]=i-1;
        nxt[i]=i+1;
    } 
}

int ceil(int x,int y){//计算x/y向上取整 
    return x/y+bool(x%y);
}

int ct(int x,int y){//计算两点什么时候相撞。 
    int k=ceil(p[y]-p[x],s[x]+s[y]);
    return 2*k-x%2;
}

void solve(){
    int n;
    cin>>n;
    init(n);
    for(int i=1;i<=n;i++)
        cin>>p[i];
    for(int i=1;i<=n;i++)
        cin>>s[i];
    priority_queue<pair<int,pair<int,int>>>q;
    //第一个int填时间（观察次数）的相反数，后面两个int存点对 
    for(int i=1;i<n;i++)
        q.push({-ct(i,i+1),{i,i+1}});//取反存入 
    while(!q.empty()){
        auto tmp=q.top();
        q.pop();
        int t=-tmp.first,x=tmp.second.first,y=tmp.second.second;
        //读出信息 
        if(a[x]||a[y])//如果之前出过队 
            continue;//跳过 
        a[x]=a[y]=t;//记录答案和vis  
        int pres=pre[x],nxts=nxt[y];
        if(pres>=1&&nxts<=n)
            q.push({-ct(pres,nxts),{pres,nxts}});//将两侧粒子入队
        //更新前驱后继 
        pre[nxts]=pres;
        nxt[pres]=nxts;
    }
    for(int i=1;i<=n;i++)
        cout<<a[i]<<" ";
    cout<<"\n";
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
//  #ifndef local
//      freopen("quantum.in","r",stdin);
//      freopen("quantum.ans","w",stdout);
//  #endif
    int t;
    cin>>t;
    for(int i=1;i<=t;i++)
        solve();
    return 0;
}