JZOJ_4737. 金色丝线将瞬间一分为二 (Standard IO)

Description

Input

Output

Solution

首先，每个点的横纵坐标相互独立，所以可以分开来做。先考虑一个 n log^2 n 的做法：二分答案 ans，将前 1~ans 个数排序，然后对于第 i 个数 x，它的贡献是 i*x-sum[i]，sum[i] 表示排序后前 i 个数的和。注意到这个做法的时间浪费在 log n 次排序上，而排序的时间复杂度是 n log n 的。我们可以一开始先将 n 个点进行 n log n 的排序，然后再 O(N)算出每个数的排名，这样在二分答案中的排序就可以做到 O(N)（由于已经得知了每个数的排名，直接使用小学生排序即可）。时间复杂度 O(N log N)。

代码

  1 var
  2   m:int64;
  3   n:longint;
  4   a,b,x,y:array [0..600001] of longint;
  5 procedure qsort1(l,r:longint);
  6 var
  7   i,j,mid,t:longint;
  8 begin
  9   if l>r then exit;
 10   i:=l; j:=r;
 11   mid:=x[(l+r) div 2];
 12   repeat
 13     while x[i]<mid do inc(i);
 14     while x[j]>mid do dec(j);
 15     if i<=j then
 16       begin
 17         t:=x[i]; x[i]:=x[j]; x[j]:=t;
 18         t:=a[i]; a[i]:=a[j]; a[j]:=t;
 19         inc(i); dec(j);
 20       end;
 21   until i>j;
 22   qsort1(i,r);
 23   qsort1(l,j);
 24 end;
 25 
 26 procedure qsort2(l,r:longint);
 27 var
 28   i,j,mid,t:longint;
 29 begin
 30   if l>r then exit;
 31   i:=l; j:=r;
 32   mid:=y[(l+r) div 2];
 33   repeat
 34     while y[i]<mid do inc(i);
 35     while y[j]>mid do dec(j);
 36     if i<=j then
 37       begin
 38         t:=y[i]; y[i]:=y[j]; y[j]:=t;
 39         t:=b[i]; b[i]:=b[j]; b[j]:=t;
 40         inc(i); dec(j);
 41       end;
 42   until i>j;
 43   qsort2(i,r);
 44   qsort2(l,j);
 45 end;
 46 
 47 procedure init;
 48 var
 49   i:longint;
 50   o,p:array [0..600001] of longint;
 51 begin
 52   readln(n,m);
 53   for i:=1 to n do
 54     begin
 55       a[i]:=i; b[i]:=i;
 56       readln(x[i],y[i]);
 57     end;
 58   qsort1(1,n);
 59   qsort2(1,n);
 60 end;
 61 
 62 function fd(ans:longint):boolean;
 63 var
 64   i,max:longint;
 65   t1,t2,num,sum1,sum2:int64;
 66 begin
 67   num:=0; t1:=0; t2:=0; sum1:=0; sum2:=0;
 68   for i:=1 to n do
 69     begin
 70       if (a[i]<=ans) and (t1<=ans) then
 71         begin
 72           inc(t1);
 73           sum1:=sum1+x[i];
 74           num:=num+t1*x[i]-sum1;
 75           if num>m then exit(true);
 76         end;
 77       if (b[i]<=ans) and (t2<=ans) then
 78         begin
 79           inc(t2);
 80           sum2:=sum2+y[i];
 81           num:=num+t2*y[i]-sum2;
 82           if num>m then exit(true);
 83         end;
 84     end;
 85   exit(false);
 86 end;
 87 
 88 procedure main;
 89 var
 90   mid,l,r:longint;
 91 begin
 92   l:=1; r:=n;
 93   while l<r do
 94     begin
 95       mid:=(l+r) div 2;
 96       if fd(mid) then r:=mid
 97                  else l:=mid+1;
 98     end;
 99   if fd(n) then writeln(l)
100            else writeln('-1');
101 end;
102 
103 begin
104   init;
105   main;
106 end.