(双指针) bzoj 1071

1071: [SCOI2007]组队

Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 1267 Solved: 392
[Submit][Status][Discuss]

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

HINT

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

Source

N^N的复杂度啊。。。据说暴力也可以过2333333

先膜拜一下18357大神ORZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>
#include<algorithm>
using namespace std;
int n,A,B,C,maxx,minn;
struct node
{
    int h,v,sum;
}e[2][5005];
bool cmp1(node a,node b)
{
    return a.h<b.h;
}
bool cmp2(node a,node b)
{
    return a.sum<b.sum;
}
bool check(int id,int val)
{
    return (e[id][val].v<=maxx)&&(e[id][val].v>=minn);
}
int main()
{
    int ans=0;
    scanf("%d%d%d%d",&n,&A,&B,&C);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&e[0][i].h,&e[0][i].v);
        e[0][i].sum=A*e[0][i].h+B*e[0][i].v;
        e[1][i]=e[0][i];
    }
    sort(e[0]+1,e[0]+1+n,cmp1);
    sort(e[1]+1,e[1]+1+n,cmp2);
    for(int i=1;i<=n;i++)
    {
        minn=e[0][i].v,maxx=minn+C/B;
        int l=0,r=0,cnt=0;
        for(int j=1;j<=n;j++)
        {
            while(r<n&&e[1][r+1].sum-A*e[0][j].h-B*e[0][i].v<=C)
            {
                cnt+=check(1,++r);
            }
            while(l<n&&e[0][l+1].h<e[0][j].h)
            {
                cnt-=check(0,++l);
            }
            ans=max(ans,cnt);
        }
    }
    printf("%d
",ans);
    return 0;
}