题解 P1296 【奶牛的耳语】

McGrady · 2017-02-03 15:56:21 · 题解

题解全是最坏情况为O(nlogn+n^2)的算法，很容易被卡掉啊

我给一个O(nlogn+n)的算法

先排序，但后来扫描的时候j不需要每次从i+1开始，比如1可以传到2,3,4,5，那么2一定能传到3,4,5，就不用再判断了，只要把j向后移就行了

所以就有了一个O(n)的扫描算法（好像看上去有点类似尺取）

代码(pascal党表示没有stl的sort，还要手写快排)：

program rrr(input,output);
var
  a:array[0..1000000]of longint;
  i,j,n,d,ans:longint;
procedure sort(q,h:longint);
var
  i,j,x,t:longint;
begin
   i:=q;j:=h;x:=a[(i+j)>>1];
   repeat
     while a[i]<x do inc(i);
     while x<a[j] do dec(j);
     if i<=j then
        begin
           t:=a[i];a[i]:=a[j];a[j]:=t;
           inc(i);dec(j);
        end;
   until i>j;
   if j>q then sort(q,j);
   if i<h then sort(i,h);
end;
begin
   //assign(input,'r.in');assign(output,'r.out');reset(input);rewrite(output);
   readln(n,d);
   for i:=1 to n do read(a[i]);
   sort(1,n);
   ans:=0;
   j:=1;
   for i:=1 to n-1 do
      begin
         while (a[j+1]-a[i]<=d) and (j<n) do inc(j);
         ans:=ans+j-i;
      end;
   write(ans);
   //close(input);close(output);
end.