OI Problems   关于

碰撞时间计算

先考虑如何计算两辆车相撞时间。只需按照两辆车速度的正负分为相遇和追及两种情况讨论即可。

  代码
namespace System{
    Frac calcTime(int x,int y){
        if(x>y)swap(x,y);
        if((a[x].v>0&&a[y].v>0)||(a[x].v<0&&a[y].v<0)){
            if(a[x].v>a[y].v)return makeFrac(a[y].p-a[x].p,a[x].v-a[y].v);
            else return makeFrac(l+a[x].p-a[y].p,a[y].v-a[x].v);
        }
        else{
            if(a[x].v>0)return makeFrac(a[y].p-a[x].p,a[x].v-a[y].v);
            else return makeFrac(l+a[x].p-a[y].p,a[y].v-a[x].v);
        }
    }
}

一些观察与思考

考虑从第一次相撞的两辆赛车入手。 容易知道第一次相撞一定是相邻的两个。（这是因为若不与相邻两个相撞，就永远在它们两个之间。）所以只需枚举相邻的两辆车计算出相撞时间即可。

设第一次 r1r_1 出局，接着考虑第二次相撞。显然，该情形等价于 1, 2, ⋯, r1−1, r1+1, r1+2, ⋯, n1,\ 2,\ \cdots,\ r_1-1,\ r_1+1,\ r_1+2,\ \cdots,\ n 这 n−1n-1 辆车的第一次相撞。（这是因为第二次相撞与 r1r_1 无关。）

同样，我们需要计算出相邻两项的相撞时间，即 1−2, 2−3, ⋯, (r1−2)−(r1−1), (r1−1)−(r1+1), (r1+1)−(r1+2), (r1+2, r1+3), ⋯, (n−1)−n, n−11-2,\ 2-3,\ \cdots,\ (r_1-2)-(r_1-1),\ (r_1-1)-(r_1+1),\ (r_1+1)-(r_1+2),\ (r_1+2,\ r_1+3),\ \cdots,\ (n-1)-n,\ n-1 的相撞时间。类似的，我们写出第一次相撞时要计算的碰撞时间：1−2, 2−3, ⋯, (r1−2)−(r1−1), (r1−1)−r1, r1−(r1+1), (r1+1)−(r1+2), (r1+2, r1+3), ⋯, (n−1)−n, n−11-2,\ 2-3,\ \cdots,\ (r_1-2)-(r_1-1),\ (r_1-1)-r_1,\ r_1-(r_1+1),\ (r_1+1)-(r_1+2),\ (r_1+2,\ r_1+3),\ \cdots,\ (n-1)-n,\ n-1。观察发现只是将 (r1−1)−r1, r1−(r1+1)(r_1-1)-r_1,\ r_1-(r_1+1) 变成了 (r1−1)−(r1+1)(r_1-1)-(r_1+1)，其结构与链表极其类似。


解法

考虑建出一个循环链表，将相邻两辆赛车的相撞时间等数据加入待选目标中。

每次（设为第 ii 次）从待选目标中选出时间最小的，此时会有赛车 rir_i 出局，这时候将 preri−ripre_{r_i}-r_i 和 ri−nxtrir_i-nxt_{r_i} 从待选目标中删去，再加入 preri−nxtripre_{r_i}-nxt_{r_i} 即可。并且将链表中的 rir_i 删去即可。

  代码
// 2023.07.22

#include<bits/stdc++.h>
using namespace std;

struct Frac{
    int x,y;
    bool operator<(Frac tmp)const{
        return 1ll*x*tmp.y<1ll*tmp.x*y;
    }
    bool operator==(Frac tmp)const{
        return 1ll*x*tmp.y==1ll*tmp.x*y;
    }
};
Frac makeFrac(int x,int y){
    return {x/__gcd(x,y),y/__gcd(x,y)};
}

int n,l;
struct Car{
    int p,v,a;
    bool operator<(Car tmp)const{
        return p<tmp.p;
    }
}a[200001];

struct BOMB{
    Frac time;
    int u,v;
    bool operator<(BOMB tmp)const{
        if(time==tmp.time)return u<tmp.u;
        else return time<tmp.time;
    }
};

set<BOMB> S;

namespace System{
    Frac calcTime(int x,int y){
        if(x>y)swap(x,y);
        if((a[x].v>0&&a[y].v>0)||(a[x].v<0&&a[y].v<0)){
            if(a[x].v>a[y].v)return makeFrac(a[y].p-a[x].p,a[x].v-a[y].v);
            else return makeFrac(l+a[x].p-a[y].p,a[y].v-a[x].v);
        }
        else{
            if(a[x].v>0)return makeFrac(a[y].p-a[x].p,a[x].v-a[y].v);
            else return makeFrac(l+a[x].p-a[y].p,a[y].v-a[x].v);
        }
    }
}

void updateRemove(int x,int y){
    if(x>y)swap(x,y);
    S.erase({System::calcTime(x,y),x,y});
}
void updateInsert(int x,int y){
    if(x>y)swap(x,y);
    S.insert({System::calcTime(x,y),x,y});
}

int nxt[200001],pre[200001];

int main(){
    scanf("%d%d",&n,&l);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i].p);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i].v);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i].a);
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++)
        nxt[i]=i+1,pre[i]=i-1;
    pre[1]=n,nxt[n]=1;
    for(int i=1;i<=n;i++)
        updateInsert(i,nxt[i]);
    for(int i=1;i<=n-2;i++){
        int u=(*S.begin()).u,v=(*S.begin()).v;
        int loser=a[u].a<a[v].a?u:v;
        updateRemove(loser,pre[loser]);
        updateRemove(loser,nxt[loser]);
        updateInsert(pre[loser],nxt[loser]);
        nxt[pre[loser]]=nxt[loser],
        pre[nxt[loser]]=pre[loser];
    }
    printf("%d/%d\n",(*S.begin()).time.x,(*S.begin()).time.y);
    return 0;
}