Description

NBA每年都有球员选秀环节。通常用速度和身高两项数据来衡量一个篮球运动员的基本素质。假如一支球队里速度最慢的球员速度为minV,身高最矮的球员高度为minH,那么这支球队的所有队员都应该满足: A * ( height – minH ) + B * ( speed – minV ) <= C 其中A和B,C为给定的经验值。这个式子很容易理解,如果一个球队的球员速度和身高差距太大,会造成配合的不协调。 请问作为球队管理层的你,在N名选秀球员中,最多能有多少名符合条件的候选球员。
Input

第一行四个数N、A、B、C 下接N行每行两个数描述一个球员的height和speed
Output

最多候选球员数目。
Sample Input
4 1 2 10
5 1
3 2
2 3
2 1
Sample Output
4

HINT

数据范围: N <= 5000 ,height和speed不大于10000。A、B、C在长整型以内。

做了这道题,我深深的体会到了longint和int64时间上的差异(因为最开始用的是int64,怕乘起来会爆longint)

现在开始分析题目

把那个式子变一下,就变成了a*x+b*y<=c+a*minx+b*miny(注意x>=minx,y>=miny)

我们暴力的想法是O(n^3)先枚举minx和miny,再枚举可行的点

因为a*x+b*y是定值,所以我们先排序,在枚举枚举minx时把比minx小的点删掉,枚举miny的时候把比miny小的点删掉(注意不要重复删除)

然后可以用树状数组维护和的信息,这样是O(n^2*logn)的

但是我们可以做得更好,我们从小到大枚举minx和miny,minx确定后c+a*minx+b*miny是递增的,所以只要拿一个指针往后移加到sum里去就行了(确定minx后把信息全部赋为初值)

这样就是O(n^2)的,用pascal的同学千万别用int64,用longint快一些,int64TLE无数

 const
maxn=;
type
aa=array[..maxn]of longint;
var
n,num,a,b,c:longint;
x,y,z,k,yi,zi:aa; procedure swap(var x,y:longint);
var
t:longint;
begin
t:=x;x:=y;y:=t;
end; procedure sort(l,r:longint;var a,b:aa);
var
i,j,y:longint;
begin
i:=l;
j:=r;
y:=a[(l+r)>>];
repeat
while a[i]<y do
inc(i);
while a[j]>y do
dec(j);
if i<=j then
begin
swap(a[i],a[j]);
swap(b[i],b[j]);
inc(i);
dec(j);
end;
until i>j;
if i<r then sort(i,r,a,b);
if j>l then sort(l,j,a,b);
end; procedure init;
var
i:longint;
begin
read(n,a,b,c);
for i:= to n do
read(x[i],y[i]);
sort(,n,x,y);
for i:= to n do
begin
k[i]:=y[i];
yi[i]:=i;
end;
sort(,n,k,yi);
for i:= to n do
begin
k[i]:=i;
zi[i]:=a*x[i]+b*y[i];
end;
sort(,n,zi,k);
for i:= to n do
if (zi[i]=zi[i-]) and (i<>) then z[k[i]]:=z[k[i-]]
else z[k[i]]:=z[k[i-]]+;
num:=;
for i:= to n do
if zi[i]<>zi[i-] then
begin
inc(num);
zi[num]:=zi[i];
end;
end; var
vis:array[..maxn]of boolean; procedure work;
var
ans,sum,i,j,l,p:longint;
begin
ans:=;
for i:= to n do
begin
if (i=) or (x[i]<>x[i-]) then
begin
sum:=;
l:=;
for j:= to num do
k[j]:=;
for j:=i to n do
inc(k[z[j]]);
for j:= to n do
if vis[yi[j]]=false then
begin
p:=c+a*x[i]+b*y[yi[j]];
while (zi[l+]<=p)and(l<num) do
begin
inc(l);
inc(sum,k[l]);
end;
if ans<sum then ans:=sum;
if zi[l]>=a*x[yi[j]]+b*y[yi[j]] then dec(sum);
dec(k[z[yi[j]]]);
end;
end;
vis[i]:=true;
if i+ans>n then break;
end;
write(ans);
end; begin
init;
work;
end.
05-11 13:19