Description
Input
Output
Sample Input
5 10
1 1
2 2
3 3
4 4
5 5
Sample Output
4
Data Constraint
Hint
题解
该题题目大意很明了，只是有些诡异的气氛。
此题第一眼看上去好像很难搞。
但是，我们要相信自己，那么再看第二眼。
我们发现，对于两点距离，可以把x坐标与y坐标分开来看。
什么意思？就是一个点(x,y)与另一个点(a,b)
他们的距离是：|x-a|+|y-b|
这样x坐标与y坐标互不干扰。
我们发现，两点之间的距离是可以分成x坐标与y坐标来求的。
于是，直观的想法——
离散化一下，然后把x坐标与y坐标按照时间，加入离散化之后数据结构（线段树/树状数组）的位置。
这样，每次查询，我们就把x坐标左边与右边的点对x的贡献求出来，y同理，然后再把x与y加入数据结构。
这样子，我们可以在O(n log n*k)（k是常数）的时间复杂度内求出答案。
实则常数很大，你很难卡常数，树状数组则优秀一些，但是还是很难卡过去（时间只有1s）
某些C选手用O3等神奇优化水过，然而P选手只能祝出题人身体健康。
标程
其中一些神奇的判断是针对部分分打的，所以不要误解。
const up=600000;
type
arr=array[0..up] of longint;
var
i,j,k,l,n,mx,my,zd,zx:longint;
now,ans,sum,op,m:int64;
tree:array[1..4*up,1..2] of int64;
gs:array[1..4*up,1..2] of longint;
x,y,jx,jy,bhx,bhy:arr;
flag:boolean;
function min(x,y:longint):longint;
begin
if x<y then exit(x);
exit(y);
end;
function max(x,y:longint):longint;
begin
if x>y then exit(x);
exit(y);
end;
procedure insert(x,l,r,p,q,num:longint);
var
m:longint;
begin
if l=r then
begin
tree[x,q]:=num;
gs[x,q]:=1;
end
else
begin
m:=(l+r) div 2;
if p<=m then insert(x*2,l,m,p,q,num)
else insert(x*2+1,m+1,r,p,q,num);
tree[x,q]:=tree[x*2,q]+tree[x*2+1,q];
gs[x,q]:=gs[x*2,q]+gs[x*2+1,q];
end;
end;
procedure find(x,l,r,st,en,p:longint);
var
m:longint;
begin
if (l=st) and (r=en) then
begin
ans:=ans+tree[x,p];
sum:=sum+gs[x,p];
end
else
begin
m:=(l+r) div 2;
if en<=m then find(2*x,l,m,st,en,p)
else if st>m then find(2*x+1,m+1,r,st,en,p)
else
begin
find(2*x,l,m,st,m,p);
find(2*x+1,m+1,r,m+1,en,p);
end;
end;
end;
procedure discretize(var a:arr);
var
i,j,k,l:longint;
b,c:arr;
procedure qsort(l,r:longint);
var
i,j,k,m:longint;
begin
i:=l;j:=r;
m:=a[(l+r) div 2];
repeat
while a[i]<m do inc(i);
while a[j]>m do dec(j);
if i<=j then
begin
k:=a[i];
a[i]:=a[j];
a[j]:=k;
k:=b[i];
b[i]:=b[j];
b[j]:=k;
inc(i);dec(j);
end;
until i>j;
if l<j then qsort(l,j);
if r>i then qsort(i,r);
end;
begin
fillchar(b,sizeof(b),0);
fillchar(c,sizeof(c),0);
for i:=0 to n do b[i]:=i;
qsort(0,n);
c[b[0]]:=0;
j:=0;
for i:=1 to n do
begin
inc(j);
c[b[i]]:=j;
end;
my:=0;
j:=0;
for i:=1 to n do
begin
if a[i]<>a[i-1] then
begin
inc(j);
inc(my);
end
end;
fillchar(a,sizeof(a),0);
for i:=0 to n do a[i]:=c[i];
bhy:=b;
end;
begin
zx:=maxlongint;
flag:=false;
readln(n,m);
for i:=1 to n do
begin
readln(x[i],y[i]);
zd:=max(zd,x[i]);
zx:=min(zx,x[i]);
if (i>1) and ((x[i-1]>x[i]) or (y[i-1]>y[i])) then
flag:=true;
end;
now:=0;
jx:=x;jy:=y;
discretize(x);
bhx:=bhy;
mx:=my;
discretize(y);
if zd=zx then
begin
insert(1,1,n,y[1],2,jy[1]);
for i:=2 to n do
begin
ans:=0;
sum:=0;
if y[i]-1>0 then
find(1,1,n,1,y[i]-1,2);
op:=sum*jy[i]-ans;
ans:=0;
sum:=0;
if y[i]+1<=n then
find(1,1,n,y[i]+1,n,2);
op:=op+ans-sum*jy[i];
now:=now+op;
if now>m then
begin
writeln(i);
break;
end;
insert(1,1,n,y[i],2,jy[i]);
end;
if now<=m then
begin
writeln(-1);
end;
end
else
if not flag then
begin
insert(1,1,n,x[1],1,jx[1]);
insert(1,1,n,y[1],2,jy[1]);
for i:=2 to n do
begin
ans:=0;
sum:=0;
if x[i]-1>0 then
find(1,1,n,1,x[i]-1,1);
op:=sum*jx[i]-ans;
ans:=0;
sum:=0;
if y[i]-1>0 then
find(1,1,n,1,y[i]-1,2);
op:=op+sum*jy[i]-ans;
now:=now+op;
if now>m then
begin
writeln(i);
break;
end;
insert(1,1,n,x[i],1,jx[i]);
insert(1,1,n,y[i],2,jy[i]);
end;
if now<=m then
begin
writeln(-1);
end;
end
else
begin
insert(1,1,n,x[1],1,jx[1]);
insert(1,1,n,y[1],2,jy[1]);
for i:=2 to n do
begin
ans:=0;
sum:=0;
if x[i]-1>0 then
find(1,1,n,1,x[i]-1,1);
op:=sum*jx[i]-ans;
ans:=0;
sum:=0;
if y[i]-1>0 then
find(1,1,n,1,y[i]-1,2);
op:=op+sum*jy[i]-ans;
ans:=0;
sum:=0;
if x[i]+1<=n then
find(1,1,n,x[i]+1,n,1);
op:=op+ans-sum*jx[i];
ans:=0;
sum:=0;
if y[i]+1<=n then
find(1,1,n,y[i]+1,n,2);
op:=op+ans-sum*jy[i];
now:=now+op;
if now>m then
begin
writeln(i);
break;
end;
insert(1,1,n,x[i],1,jx[i]);
insert(1,1,n,y[i],2,jy[i]);
end;
if now<=m then
begin
writeln(-1);
end;
end;
end.
答案是可以的。
我们换一种思路，我们可以二分一下答案，然后，我们就要判断在这个答案下，满不满足要求即可。
那么我们直观的思路——
二分，然后再把当前答案之前那些点排序，然后计算距离和。
那么我们看看：
由于排完序了，那么这个序列是递增的，于是，我们可以维护3个值——
sum：当前的距离和。
ans：前缀和。
那么设我们当前枚举到第i个点，于是sum+=(i-1)*x[i]-ans
什么意思？由于是递增的（这个很重要），那么我们是之前的x’走(x[i]-x’)的距离对答案贡献。
那么，化简一下就是上面的式子了。
这样就可以在O(n log^2 n*(极小的常数，可以忽略不计))
但是，多了个log很蛋疼。
其实，我们发现，每次在二分里面排序其实很蠢，我们直接在外面排个序，然后我们就可以把每个点的相应位置给记录下来，于是，我们就直接在二分里面用就好了。
时间O(n log n)nice~~~
真·标程
{$inline on}
type
arr=array[0..10000000]of longint;
var
i,j,k,l,n:longint;
m,sum,num,ans:int64;
x,y,bhx,bhy:arr;
function pd(m:longint):int64;inline;
var
i:longint;
ans,sum:int64;
begin
ans:=0;
sum:=0;
for i:=1 to n do
begin
if bhx[i]<=n then
begin
inc(sum,(i-1)*x[i]-ans);
inc(ans,x[i]);
end;
end;
ans:=0;
for i:=1 to n do
begin
if bhy[i]<=n then
begin
inc(sum,(i-1)*y[i]-ans);
inc(ans,y[i]);
end;
end;
end;
procedure erfen;inline;
var
l,r,mid:longint;
begin
l:=2;
r:=n;
while l < r do
begin
mid:=(l+r)div 2;
if pd(mid)>m then
begin
r:=mid;
end
else
begin
l:=mid+1;
end;
end;
writeln(l);
end;
procedure qsort(i,j:longint;var x,bh:arr);inline;
var
l,r,m:longint;
begin
l:=i;
r:=j;
m:=x[(i+j)div 2];
repeat
while x[i]<m do inc(i);
while x[j]>m do dec(j);
if i<=j then
begin
bh[0]:=bh[i];
bh[i]:=bh[j];
bh[j]:=bh[0];
x[0]:=x[i];
x[i]:=x[j];
x[j]:=x[0];
inc(i);
dec(j);
end;
until i>j;
if i<r then qsort(i,r,x,bh);
if l<j then qsort(l,j,x,bh);
end;
begin
//assign(input,'cut.in');reset(input);
readln(n,m);
for i:=1 to n do
begin
readln(x[i],y[i]);
end;
for i:=1 to n do
begin
bhx[i]:=i;
bhy[i]:=i;
end;
qsort(1,n,x,bhx);
qsort(1,n,y,bhy);
ans:=0;
sum:=0;
for i:=1 to n do
begin
if bhx[i]<=n then
begin
inc(sum,(i-1)*x[i]-ans);
inc(ans,x[i]);
end;
end;
ans:=0;
for i:=1 to n do
begin
if bhy[i]<=n then
begin
inc(sum,(i-1)*y[i]-ans);
inc(ans,y[i]);
end;
end;
if sum<=m then
begin
writeln(-1);
end
else
begin
erfen;
end;
end.
十个表过去，O(1)
