刷题总结——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+;

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=,i=;

  for(c=getchar();(c<''||c>'')&&c!='-';c=getchar());

  if(c=='-')  c=getchar(),i=-;

  for(;c<=''&&c>='';c=getchar())  f=(f<<)+(f<<)+c-'';

  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==)  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=;i<=n;i++)  p[i].po=R(),p[i].id=i;

    for(int i=;i<=n;i++)  p[i].v=R();

    sort(p+,p+n+,cmp);

    for(int i=;i<=n;i++)  le[i]=i-,ri[i]=i+;

    le[]=n,ri[n]=;

    for(int i=;i<=n;i++)  que.push((node1){i,ri[i],calc(i,ri[i])});

    for(int i=;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>)  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 ;

}

巴特西

刷题总结——run（ssoj）

题目：

题目描述

输入格式

输出格式

样例数据 1

备注

题解：

代码：

最新文章

热门文章