题意：
有n个人在一个环形的跑道上，第i个人有一个power i，每个人有一个起始点和一个不同的速度。
如果两个人相遇，那么power大的那个人就会将power小的那个人淘汰出局。
然后问决出胜负需要多少时间。
题解：
显然，每次有人被淘汰出局的时候，都是被相邻的人干掉的，那么我们先预处理出相邻的人相遇的时间，然后扔进优先队列里面，每次选择最小的时间，将一个人淘汰掉，然后再更新一下当前的局势就行了。
1 #include<bits/stdc++.h> 2 #define F(i,a,b) for(int i=(a);i<=(b);++i) 3 using namespace std; 4 typedef pair<int,int>P; 5 6 const int N=1e5+7; 7 int t,n,L,head,vis[N],rev[N],TIM; 8 9 struct VAL 10 { 11 int a,b,x,y;double val; 12 VAL(){} 13 VAL(int _a,int _b,int _x,int _y):a(_a),b(_b),x(_x),y(_y){val=1.0*_a/_b;} 14 bool operator <(const VAL&B)const{return val>B.val;} 15 }; 16 struct LIST{int idx,pre,nxt;}lst[N]; 17 P a[N],tmp[N]; 18 priority_queue<VAL>Q; 19 20 VAL cal(int x,int y) 21 { 22 if(a[x].first>a[y].first)swap(x,y); 23 int dis,V=abs(a[x].second-a[y].second); 24 if(a[x].second>a[y].second) 25 dis=a[y].first-a[x].first; 26 else dis=L-a[y].first+a[x].first; 27 int gcd=__gcd(dis,V); 28 dis/=gcd,V/=gcd; 29 return VAL(dis,V,x,y); 30 } 31 32 void del(int x,int y) 33 { 34 int lx=rev[x],ly=rev[y]; 35 if(lst[lx].pre==ly) 36 { 37 lst[lx].pre=lst[ly].pre; 38 lst[lst[ly].pre].nxt=lx; 39 Q.push(cal(x,lst[lst[ly].pre].idx)); 40 }else 41 { 42 lst[lx].nxt=lst[ly].nxt; 43 lst[lst[ly].nxt].pre=lx; 44 Q.push(cal(x,lst[lst[ly].nxt].idx)); 45 } 46 } 47 48 int main(){ 49 scanf("%d",&t); 50 while(t--) 51 { 52 TIM++,scanf("%d%d",&n,&L); 53 F(i,1,n)scanf("%d",&a[i].first); 54 F(i,1,n)scanf("%d",&a[i].second); 55 F(i,1,n)tmp[i]=P(a[i].first,i); 56 sort(tmp+1,tmp+1+n),head=1; 57 F(i,1,n)lst[i]=LIST{tmp[i].second,i-1,i+1},rev[tmp[i].second]=i; 58 lst[n].nxt=1,lst[1].pre=n; 59 while(!Q.empty())Q.pop(); 60 F(i,1,n)Q.push(cal(lst[i].idx,lst[lst[i].nxt].idx)); 61 VAL ans; 62 F(i,2,n) 63 { 64 VAL now=Q.top();Q.pop(); 65 while(vis[now.x]==TIM||vis[now.y]==TIM) 66 now=Q.top(),Q.pop(); 67 if(i==n)ans=now; 68 int x=now.x,y=now.y; 69 if(x<y)swap(x,y); 70 del(x,y),vis[y]=TIM; 71 } 72 printf("%d/%d ",ans.a,ans.b); 73 } 74 return 0; 75 }