【题目链接】 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;
}
05-11 20:18