题解 P1296 【奶牛的耳语】

嚯呀嚯呀 · 2018-08-17 07:45:05 · 题解

其实这题有O(n)的做法的，用不到之前dalao说的二分啊之类的......

首先先把位置排序(我一开始以为是默认有序的，结果WA)

然后先处理第1头奶牛向右最多能让第几头奶牛听到，记录指针p，和答案ans

然后枚举每一头奶牛，因为排过序了，所以第1头奶牛能传出去的后面的奶牛肯定也能传到，只要在p的基础上继续向后扩展就可以了

注意一个特殊情况，如果一个奶牛不能向右传出去到任何一个奶牛(就是它后面的奶牛都离它巨远)，这时候p要指向下一头奶牛，不然会出现p<枚举的i的情况，出现错误

Code(Pascal 福利！！)：

var
  ans:int64;
  d,i,j,m,n,k,p:longint;
  a:array[0..1000005]of longint;
procedure qs(l,r:longint);
var
  i,j,mid,a1:longint;
begin
  i:=l; j:=r;
  mid:=a[(l+r) div 2];
  repeat
    while a[i]<mid do inc(i);
    while a[j]>mid do dec(j);
    if not(i>j) then
      begin
        a1:=a[i]; a[i]:=a[j]; a[j]:=a1;
        inc(i); dec(j);
      end;
  until i>j;
  if i<r then qs(i,r);
  if l<j then qs(l,j); 
end;
begin
  readln(n,d);
  for i:=1 to n do
    read(a[i]);
  qs(1,n);//好羡慕你们C++啊
  for i:=2 to n do
    begin
      if a[i]-a[1]<=d then
        inc(ans)
      else
        begin
          p:=i-1; break;
        end;
    end;
  for i:=2 to n do
    begin
      //ans:=ans+p-i;
      while (p+1<=n)and(a[p+1]-a[i]<=d) do
        inc(p);
      ans:=ans+p-i;
      if p=i then p:=i+1;
    end;
  writeln(ans);
end.