在一个带起点的圆形轨道上,有很多点以一定的速度沿着该轨道顺时针或者逆时针运动。给出所有点的初始位置和各自的速度,求经过时间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