题目描述
给定一个长度为L的环形赛道, n个人在上面赛艇. 每个人的速度都不相同, 假如为正则顺时针走, 否则逆时针走. 当两个人相遇时, 编号小的那个人就会出局. 当只剩下一个人时, 这个人就获得胜利.（L<=1e9 , n<=1e5）
问: 多久以后游戏结束.
#include<bits/stdc++.h> using namespace std; int read(){ int x=0,f=1; char ch=getchar(); while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();} while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();} return x*f; } int get_gcd(int a,int b){ if(b==0) return a; return get_gcd(b,a%b); } const int N=1e5+5; int n,L; struct boat{int w,d,v;}a[N]; bool cmpd(boat a,boat b){ return a.d<b.d; } struct record{ int id[2];double t; inline record(){} inline record(int u,int v){ if(a[u].v>a[v].v) swap(u,v); t=(double)((a[u].d-a[v].d+L)%L)/(a[v].v-a[u].v);//相遇时间 id[0]=u;id[1]=v; if(a[id[0]].w<a[id[1]].w) swap(id[0],id[1]);//id[0]留下，id[1]出局 } inline int operator <(const record &a) const{return t>a.t;}//从小到大排 }; static int nxt[N],lst[N],del[N]; int main(){ n=read();L=read(); for(int i=1;i<=n;i++){ a[i].w=i;a[i].d=read(); } for(int i=1;i<=n;i++){ a[i].v=read(); } //因为每次相遇的只能是位置相邻的两人,所以把相邻两人相遇所需要的时间用一个堆维护起来 sort(a+1,a+n+1,cmpd); priority_queue<record> q; q.push(record(1,n)); for(int i=2;i<=n;i++) q.push(record(i,i-1)); for(int i=1;i<=n;i++) nxt[i]=(i+1)%n==0?n:(i+1)%n; for(int i=1;i<=n;i++) lst[i]=(i-1)%n==0?n:(i-1)%n; //每次找到最早相遇的两个人,记录其中一人出局,并将新产生的相邻的两人加入堆中 for(int i=n;i>=3;i--){ record rec; while(1){ rec=q.top();q.pop(); int pd=1; if(del[rec.id[0]]||del[rec.id[1]]) pd=0; if(pd) break; } del[rec.id[1]]=1; nxt[lst[rec.id[1]]]=nxt[rec.id[1]]; lst[nxt[rec.id[1]]]=lst[rec.id[1]]; nxt[rec.id[1]]=lst[rec.id[1]]=-1; q.push(record(rec.id[0],nxt[rec.id[0]])); q.push(record(rec.id[0],lst[rec.id[0]])); //可能在前面也可能在后面产生新的相邻两人 } record rec; while(1){ rec=q.top();q.pop(); int pd=1; if(del[rec.id[0]]||del[rec.id[1]]) pd=0; if(pd) break; } //得到最后是哪两人相遇 if(a[rec.id[0]].v>a[rec.id[1]].v) swap(rec.id[0],rec.id[1]); int ans1=(a[rec.id[0]].d-a[rec.id[1]].d+L)%L; int ans2=a[rec.id[1]].v-a[rec.id[0]].v; if(ans1==0||ans2==0) printf("0 "); else{ int gcd=get_gcd(ans1,ans2); printf("%d/%d",ans1/gcd,ans2/gcd); } return 0; }