bzoj1071: [SCOI2007]組隊

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在長整型以内。

2016.3.26 資料加強 Nano_ape 程式未重測

思路

這題資料被進行了加強

是以現在需要開long long

先給sum = A * h + B * s排序，然後枚舉h和s的最小值。(h – Height, s – Speed)

然後就是兩個指針亂搞：

先枚舉s最小值，然後一邊枚舉v的最小值一邊查詢符合條件的人數，因為這一定是相鄰的一串。

PS：盡量不要用快讀，要用scanf（不知是不是我的快讀有毒）

代碼

#include <cstdio>
#include <algorithm>
#include <iostream>
#define max(x,y) (x>y?x:y)
#define int long long
using namespace std;
struct pppp{int s,h,sum;}x[],y[];
bool cmp(pppp x,pppp y){return x.h<y.h;}
bool cmp1(pppp x,pppp y){return x.sum<y.sum;}
int n,A,B,C,m1,m2,l,r,pp,ans=;
inline bool check1(int p){
    return y[p].s <= m2 && y[p].s >= m1;
}
inline bool check2(int p){
    return x[p].s <= m2 && x[p].s >= m1;
}
main(){
    scanf("%lld", &n);
    scanf("%lld%lld%lld", &A, &B, &C);
    for(int i=;i<=n;++i){
        scanf("%lld%lld", &x[i].h, &x[i].s); 
        x[i].sum=A*x[i].h+B*x[i].s;
        y[i]=x[i];
    }
    sort(x+,x+n+,cmp);
    sort(y+,y+n+,cmp1);
    for(int i=;i<=n;++i){
        m1=x[i].s;m2=m1+C/B;
        l=r=pp=;
        for(int j=;j<=n;++j){
            while(r<n&&y[r+].sum<=A*x[j].h+B*x[i].s+C)++r,pp+=check1(r);
            while(l<n&&x[l+].h<x[j].h)++l,pp-=check2(l);
            ans=max(ans,pp);
        }
    }
    printf("%d\n",ans);
    return ;
}