死国矣……

$v$表示速度,$h$表示高度,$s=Ah+Bv$,约束条件化为 $Ah+Bv \leq C+Aminh+Bminv$

搞两个数组,$a$按照 $h$从小到大排序,$b$按照 $s$从小到大排序。

任意顺序枚举 $minv$,开两个指针 $l$和 $r$,分别指着 $a$和 $b$的开头。

按照递增的顺序枚举 $minh$。

如果 $b(r)_s \leq C+Aminh+Bminv$,就将 $r$指针后移。如果 $minv \leq b(r)_v \leq \frac{C}{B}+minv$(这个 $r$是移动前的),就令当前统计的球员数量++

如果 $a(l)_h < minh$,则将 $l$指针左移,并在左移前判断如果 $minv \leq a(l)_v \leq \frac{C}{B}+minv$

你可能会说,$minv \leq v$这个条件没问题,但是为什么一定要 $v \leq \frac{C}{B}+minv$呢?

首先,若 $v \leq \frac{C}{B}+minv$,则 $B(v-minv) \leq C$,对任意一个 $h<minh$,都有 $A(h-minh)+B(v-minv) \leq C$,我们不会减掉没有出现过的答案。

那为什么不在去除答案的时候判断 $s \leq C+Aminh+Bminv$呢?因为可能你移到某个 $l$时,依然 $a(l)_s > Aminh+Bminv+C$但 $a(l)_h < minh$,于是就没有减去贡献,就会使算出来的答案偏大。

#include<bits/stdc++.h>
using namespace std;
#define RI register int
const int N=5005;
int n,A,B,C,ans;
struct node{int v,h,s;}a[N],b[N];
bool cmp1(node x,node y) {return x.h<y.h;}
bool cmp2(node x,node y) {return x.s<y.s;}
int main()
{
    scanf("%d%d%d%d",&n,&A,&B,&C);
    for(RI i=1;i<=n;++i) {
        scanf("%d%d",&a[i].h,&a[i].v);
        a[i].s=A*a[i].h+B*a[i].v,b[i]=a[i];
    }
    sort(a+1,a+1+n,cmp1),sort(b+1,b+1+n,cmp2);
    for(RI i=1;i<=n;++i) {
        int minv=a[i].v,l=1,r=1,js=0;
        for(RI j=1;j<=n;++j) {
            int minh=a[j].h;
            while(r<=n&&b[r].s<=A*minh+B*minv+C) {
                if(b[r].v>=minv&&b[r].v<=C/B+minv) ++js;
                ++r;
            }
            while(l<=n&&a[l].h<minh) {
                if(a[l].v>=minv&&a[l].v<=C/B+minv) --js;
                ++l;
            }
            ans=max(ans,js);
        }
    }
    printf("%d\n",ans);
    return 0;
}
分类: 文章

litble

苟...苟活者在淡红的血色中,会依稀看见微茫的希望

1 条评论

XZYQvQ · 2018年10月30日 9:08 下午

当我在水博客的时候,大佬已经又双叒叕刷掉 $N$道题了。。。

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用 * 标注