vijos 分梨子

很有（wei）趣（suo）的一道题

暴力解法也不难，枚举大小下限与甜度下限，在一个一个地试

显然 O(n^3) 炸掉

但如何将其缩短，只好从那个式子来入手了：

C1⋅(ai−a0)+C2⋅(bi−b0)<=C3

变换一下可得：

C1⋅ai+C2⋅bi−C3<=C1⋅a0+C2⋅b0

不难发现

当甜度下限与大小下限一直增大，梨子的甜度与大小整体会增大，而小于下限的也不会再被访问到

于是从小到大枚举下限

设t[i]为当甜度下限为b[i]时，刚好可以被访问到的（意思是在前面还没被访问到）梨子的个数

代码如下：

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

int getint()

{

    int num=0,flag=1;char c;

    while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;

    while(c>='0'&&c<='9')num=num*10+c-48,c=getchar();

    return num*flag;

}

struct node{

    int num,id;

}B[2001],C[2001];

bool cmp(node x,node y){return x.num<y.num;}

int t[2001],sum,ans;

int a[2001],b[2001];

int n,c1,c2,c3;

int main()

{

    int i,j;

    n=getint();c1=getint(),c2=getint(),c3=getint();

    for(i=1;i<=n;i++)a[i]=getint(),B[i].num=b[i]=getint(),B[i].id=i;

    for(i=1;i<=n;i++)C[i].num=a[i]*c1+b[i]*c2-c3,C[i].id=i;

    sort(B+1,B+n+1,cmp);sort(C+1,C+n+1,cmp);

    for(i=1;i<=n;i++){

        memset(t,0,sizeof t);

        sum=0;

        int k=1;

        for(j=1;j<=n;j++)

        {

            while(k<=n&&a[i]*c1+B[j].num*c2>=C[k].num){

                if(a[C[k].id]>=a[i]&&b[C[k].id]>=B[j].num)

                    sum++,t[C[k].id]++;

                k++;

            }

            if(j>1)

                sum-=t[B[j-1].id],t[B[j-1].id]=0;

            ans=max(ans,sum);

        }

    }

    printf("%d",ans);

}

巴特西

vijos 分梨子

最新文章

热门文章