首页 > 其他 > 详细

相遇点对

时间:2017-01-06 10:54:04      阅读:303      评论:0      收藏:0      [点我收藏+]

在一个带起点的圆形轨道上,有很多点以一定的速度沿着该轨道顺时针或者逆时针运动。给出所有点的初始位置和各自的速度,求经过时间T以后有多少对点相遇(相遇就是它们在同一时刻处于同一位置)。

第一行3个整数L,T,N。表示有N个结点,环长度为L,和时间T。

接下来N行,每行两个整数Ki,Vi。Ki表示从起点顺时针走到达i点的距离。Vi表示i点的顺时针速度,为负数的话表示该点逆时针运动。

 

题解:

将所有点按照初始位置Ki排序,然后根据Ki+Vi*T进行CDQ分治。

对于Ki<Kj的点对,若Ki+Vi*T>=Ki+Vi*T,则会相遇;对于Ki>Kj的点对,若Ki+Vi*T+L>=Kj+Vj*T,则会相遇。

注意考虑初始位置相同的情况,这样的点对一定会相遇。

 

代码:

var
  i,j,k,l,n,m:longint;
  a,b,c:array[0..100001,1..2]of int64;
  ll,t,ans,ans2:int64;
function ef(l,r,x:int64):longint;
var ans,mid,ll,rr:longint;
begin
  if x>a[r,2] then exit(0);
  ans:=r; rr:=r-1; ll:=l;
  while ll<=rr do
  begin
    mid:=(ll+rr)div 2;
    if a[mid,2]>=x then begin ans:=mid; rr:=mid-1; end
    else ll:=mid+1;
  end;
  exit(r-ans+1);
end;
procedure cdq(l,r:longint);
var i,j,k,mid:longint;
begin
  if l=r then exit; k:=0;
  mid:=(l+r)div 2; cdq(l,mid); cdq(mid+1,r);
  i:=l; j:=mid+1;
  while(i<=mid)and(j<=r)do
  begin
    if a[i,2]<a[j,2] then
    begin
      ans:=ans+j-mid-1; ans:=ans+ef(j,r,a[i,2]+ll);
      inc(k); c[k]:=a[i]; inc(i);
    end else
    begin inc(k); c[k]:=a[j]; inc(j); end;
  end;
  if i<=mid then
  for j:=i to mid do
  begin inc(k); c[k]:=a[j]; ans:=ans+r-mid; end else
  for i:=j to r do
  begin inc(k); c[k]:=a[i]; end;
  for i:=l to r do a[i]:=c[i-l+1];
end;
procedure sort(l,r:longint);
var
  i,j:longint;
  x:int64;
  y:array[1..2]of int64;
begin
  i:=l; j:=r; x:=a[(l+r) div 2,1];
  repeat
    while a[i,1]<x do inc(i);
    while x<a[j,1] do dec(j);
    if not(i>j) then
    begin
      y:=a[i]; a[i]:=a[j]; a[j]:=y;
      inc(i); j:=j-1;
    end;
  until i>j;
  if l<j then sort(l,j);
  if i<r then sort(i,r);
end;
begin
  readln(ll,t,n);
  for i:=1 to n do
  begin
    readln(a[i,1],a[i,2]);
    a[i,1]:=a[i,1] mod ll;
    a[i,2]:=a[i,1]+t*a[i,2];
  end;
  sort(1,n);
  b:=a; i:=1; a[n+1,1]:=-1;
  while i<=n do
  begin
    j:=i;
    while a[i,1]=a[j+1,1] do inc(j);
    cdq(i,j); ans2:=ans2+(j-i)*(j-i+1)div 2;
    i:=j+1;
  end;
  ans:=ans2-ans; a:=b; cdq(1,n);
  writeln(ans);
end.

 

相遇点对

原文:http://www.cnblogs.com/GhostReach/p/6255054.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!