HDU 6136 Death Podracing（循环链表）

【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=6136

【题目大意】

　　一堆人在操场上跑步，他们都有一定的速度和初始位置，
　　当两个人相遇的时候编号较小的就会出局，当场上剩下最后一个人的时候游戏结束，
　　问时长为多少

【题解】

　　我们发现每次发生碰撞的一定是相邻的两个人，
　　所以我们找出相邻关系中最先发生碰撞的，将碰撞失败的那个人删除，
　　之后继续这个过程，
　　按照上述的做法我们建立一个循环链表，把所有人串起来，
　　当发生淘汰的时候把那个人从循环链表中删去即可，
　　用优先队列维护相邻关系，每次出队最小相遇时间即可。

【代码】

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <queue>

using namespace std;

const int N=100010,INF=0x3f3f3f3f;

struct data{int d,v,pw;}p[N];

bool cmp(data a,data b){return a.d<b.d;}

int T,Del[N],n,L,nxt[N],pre[N];

struct Frac{

    int Den,Num;

    Frac(){}

    Frac(int _Num,int _Den){Den=_Den;Num=_Num;}

    bool operator <(const Frac &rhs)const{return 1LL*Num*rhs.Den<1LL*rhs.Num*Den;}

};

Frac Cal(data a,data b){

    int V=b.v-a.v,D=a.d-b.d;

    if(D<0)D+=L; if(V<0)V=-V,D=L-D;

    if(V==0)return Frac(INF,1);

    int GCD=__gcd(V,D);

    return Frac(D/GCD,V/GCD);

}

struct Relt{

    int a,b;Frac t;

    Relt(){}

    Relt(int _a,int _b,Frac _t){a=_a;b=_b;t=_t;}

    bool operator < (const Relt &x)const{return x.t<t;}

};

priority_queue<Relt> Q;

void Out(int x){

    Del[x]=1;

    nxt[pre[x]]=nxt[x];

    pre[nxt[x]]=pre[x];

    Q.push(Relt(pre[x],nxt[x],Cal(p[pre[x]],p[nxt[x]])));

}

int main(){

    scanf("%d",&T);

    while(T--){

        scanf("%d%d",&n,&L);

        memset(Del,0,sizeof(Del));

        for(int i=0;i<n;i++)scanf("%d",&p[i].d),p[i].pw=i;

        for(int i=0;i<n;i++)scanf("%d",&p[i].v);

        sort(p,p+n,cmp); while(!Q.empty())Q.pop();

        for(int i=0;i<n;i++){

            nxt[i]=(i+1)%n; pre[i]=(i-1+n)%n;

            Q.push(Relt(i,nxt[i],Cal(p[i],p[nxt[i]])));

        }int Lft=n; Frac Ans;

        while(Q.size()){

            Relt x=Q.top(); Q.pop();

            if(Del[x.a]||Del[x.b])continue;

            if(--Lft==1){Ans=x.t;break;}

            if(p[x.a].pw>p[x.b].pw)Out(x.b);

            else Out(x.a);

       }printf("%d/%d\n",Ans.Num,Ans.Den);

    }return 0;

}