M_sea

洛谷4165 [SCOI2007]组队
LuoguBZOJ分析先拆一下式子,变成 $A\times h+B\times v\leq C+A\times m...
扫描右侧二维码阅读全文
13
2019/02

洛谷4165 [SCOI2007]组队

Luogu

BZOJ

分析

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

考虑一个暴力做法。

先枚举 $minV$ ,再枚举 $minH$ 。如果我们把所有人按 $A*h+B*v$ 排序的话那满足条件的就是单调的了。可是还有一个 $h\geq minH,v\geq minV$ 的条件,所以我们要用一个数据结构来维护。这样子是 $O(n^2\log n)$ 的。

有一个奇妙的方法,可以做到 $O(n^2)$ 。

还是枚举 $minV$ 和 $minH$ 。先把满足条件的 $v$ 加入,再把不满足条件的 $h$ 删去。

如果 $v$ 合法,那么有 $minV\leq v\leq minV+\frac{C}{B}$ ;如果 $h$ 不满足条件,那么 $h<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 年 05 月 26 日 08 : 48 PM

发表评论