刷题总结——run（ssoj）

企鹅国正在举办全面运动会，第一项比赛就是跑步。N 个人在圆形跑道上跑步，他们都有各自的速度和起点。但这个跑步规则很奇怪，当两个人相遇的时候编号较小的就会出局，当场上剩下最后一个人的时候跑步就结束了。豆豆想知道多长时间游戏会结束？

输入格式

第一行一个整数 T 表示数据组数；
每组数据的第一行是两个整数 N 和 L ，表示参赛人数以及跑道长度。
接下来一行有 N 个不同的整数 Di，表示每个人的起点。
接下来一行有 N 个不同的整数 Vi，表示每个人的跑步速度，如果速度为负数，就是在反着跑。

输出格式

对于每组数据，以最简分数形式表示游戏结束的时间。

样例数据 1

输入　 [复制]

2
2 4
0 2
3 2
10 100
56 89 62 71 7 24 83 1 47 52
9 -16 34 -38 47 49 -32 17 39 -9

输出

2/1
37/7

备注

【数据范围】
对于 30% 的数据，2≤n≤100, 1≤L≤200；
对于 60% 的数据，2≤n≤103。
对于 100% 的数据，2≤n≤105，T≤5, 1≤L≤109, 0≤Di<L, 0≤|Vi|≤109；

题解：

首先将每个人按照其位置排序··然后建立一个左右链表···

肯定是相邻的两个人先相遇···所以我们想相邻两人间的相遇时间加入到一个优先队列中···

然后每次取出对首元素,然后判断元素对应的两个人的编号大小决定删除哪一个人··然后根据这个人的左右链表加入他两旁的人的时间··并且更新链表即可··（注意用visit数组判定每个人是否被删除··如果是那么包含这个人的元素是无效的····）最后剩余的一个元素对应的两个人就是最后消除的两个人··计算答案即可···

这道题的关键是相邻的两个人先相遇···所以可以利用链表···

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<cctype>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
using namespace std;
const int N=1e5+5;
bool visit[N];
struct node
{
  int po,id,v;
}p[N];
struct node1
{
  int p1,p2;double Time;
  friend inline bool operator < (node1 a,node1 b) {return a.Time>b.Time;}
};
priority_queue<node1>que;
inline int R()
{
  char c;int f=0,i=1;
  for(c=getchar();(c<'0'||c>'9')&&c!='-';c=getchar());
  if(c=='-')  c=getchar(),i=-1;
  for(;c<='9'&&c>='0';c=getchar())  f=(f<<3)+(f<<1)+c-'0';
  return f*i;
}
int T,n,L,ri[N],le[N];
inline bool cmp(node a,node b)
{
  return a.po<b.po;
}
inline double calc(int a,int b)
{
  if(p[a].po>p[b].po)  swap(a,b);  
  if(p[a].v>p[b].v)  return (double)(p[b].po-p[a].po)/(p[a].v-p[b].v);
  else return (double)(L-p[b].po+p[a].po)/(p[b].v-p[a].v);
}
inline void del(int u)
{
  visit[u]=true;ri[le[u]]=ri[u];le[ri[u]]=le[u];
}
inline int gcd(int a,int b)
{
  if(b==0)  return a;
  else return gcd(b,a%b); 
}
inline void pre()
{
  while(!que.empty())  que.pop();memset(visit,false,sizeof(visit));
}
int main()
{
  //freopen("a.in","r",stdin);
  T=R();  
  while(T--)
  {
    pre();
    n=R(),L=R();
    for(int i=1;i<=n;i++)  p[i].po=R(),p[i].id=i;
    for(int i=1;i<=n;i++)  p[i].v=R();
    sort(p+1,p+n+1,cmp);
    for(int i=1;i<=n;i++)  le[i]=i-1,ri[i]=i+1; 
    le[1]=n,ri[n]=1;
    for(int i=1;i<=n;i++)  que.push((node1){i,ri[i],calc(i,ri[i])});
    for(int i=1;i<n;i++)
    {
      while(visit[que.top().p1]||visit[que.top().p2])  que.pop();
      node1 u=que.top();que.pop();      
      if(p[u.p1].id<p[u.p2].id)
      {
        del(u.p1);
        que.push((node1){le[u.p2],u.p2,calc(u.p2,le[u.p2])});
      }

      else
      {
        del(u.p2);
        que.push((node1){u.p1,ri[u.p1],calc(u.p1,ri[u.p1])});
      }
    }
    node1 u=que.top();int v1=p[u.p1].v,v2=p[u.p2].v,po1=p[u.p1].po,po2=p[u.p2].po;
    if(po1>po2)  swap(po1,po2),swap(v1,v2);
    if(v1-v2>0)  cout<<(po2-po1)/gcd(po2-po1,v1-v2)<<"/"<<(v1-v2)/gcd(po2-po1,v1-v2)<<endl;
    else  cout<<(L-po2+po1)/gcd(L-po2+po1,v2-v1)<<"/"<<(v2-v1)/gcd(L-po2+po1,v2-v1)<<endl;
  }
  return 0;
}