M_sea

洛谷4165 [SCOI2007]组队
LuoguBZOJ分析更清晰易懂的讲解请看$\texttt{yyb's blog}$神仙题。先拆一下式子,变成$A...
扫描右侧二维码阅读全文
13
2019/02

洛谷4165 [SCOI2007]组队

Luogu

BZOJ

分析

更清晰易懂的讲解请看$\texttt{yyb's blog}$


神仙题。

先拆一下式子,变成$A\times h+B\times v\leq C+A\times minh+B\times minv$。

我们假装枚举了$minv$,于是按照$h$和$A\times h+B\times v$排序,然后显然满足条件的是一段区间。

考虑$v$的取值范围,容易得到$minv\leq v\leq minv+\frac{C}{B}$。

然后再把区间中不满足$h\leq minh$的全部删掉,就是当前的答案了?

假装这个东西是对的

细节见代码。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=5000+10;

int n,A,B,C;
struct Player { int h,v,s; } a[N],b[N];
inline int cmph(Player x,Player y) { return x.h<y.h; }
inline int cmps(Player x,Player y) { return x.s<y.s; }
    
int main() {
    n=read(),A=read(),B=read(),C=read();
    for (re int i=1;i<=n;++i)
        a[i].h=read(),a[i].v=read(),a[i].s=A*a[i].h+B*a[i].v;
    memcpy(b,a,sizeof(b));
    sort(a+1,a+n+1,cmph); sort(b+1,b+n+1,cmps);
    int ans=0;
    for (re int i=1;i<=n;++i) {
        int minv=a[i].v,mx=minv+C/B;
        int l=0,r=0,cnt=0;
        for (re int j=1;j<=n;++j) {
            while (r<n&&b[r+1].s-A*a[j].h-B*a[i].v<=C) {
                ++r; if (b[r].v>=minv&&b[r].v<=mx) ++cnt;
            }
            while (l<n&&a[l+1].h<a[j].h) {
                ++l; if (a[l].v>=minv&&a[l].v<=mx) --cnt;
            }
            ans=max(ans,cnt);
        }
    }
    printf("%d\n",ans);
    return 0;
}
最后修改:2019 年 02 月 13 日 11 : 16 AM

发表评论