这道题也很感人,主要改了比较久的时间。。。
bzoj第一页的题,居然只过了五百多个人,(我是第512,orzliyicheng是513)
代码不长,但是细节搞了很久,主要sort写错了,晕。。。
首先根据A*h+B*s排序,依次枚举minx,miny,令now=A*minx+B*miny+C
在miny增大的同时,now也跟着增大,我们可以依次把符合的加进队
然后随着miny增大,也会出现不符合的点弹出来,height<miny,同时speed符合原来进队的条件
那么会不会出现,height<miny,而speed不符合原来进队列的条件呢?
其实是有的,但是不影响答案。
“分类讨论下
首先如果一个点满足被计数的条件即 V<=v<=V+CB ,那么如果又满足 h<H 那么有 0+B(v−V)<=C ,而A(h−H)则一定<0 。
所以 A(h−H)+B(v−V)<=C 。。。。。。所以一定加进来然后被计数过,不会减多了。然后如果不满足被计数的条件。23333,都没有被计数我们管它作甚?”
这样就满足了所有条件,AC hard...
#include<cstdio> #include<algorithm> #define N 20000 #define ll long long using namespace std; struct node{ll x,bh;}cc[N]; struct sss{ll x,bh,xx;}ss[N]; ll h[N],s[N],n,A,B,C,minx,miny,maxx; int ans,sum; bool cmp1(node a,node b) { return a.x<b.x; } bool cmp2(sss a,sss b) { return a.xx<b.xx; } int main() { scanf("%lld%lld%lld%lld",&n,&A,&B,&C); ;i<=n;i++) { scanf("%lld%lld",&h[i],&s[i]); cc[i].x=A*h[i]+B*s[i];cc[i].bh=i; ss[i].x=h[i];ss[i].bh=i;ss[i].xx=s[i]; } sort(cc+,cc+n+,cmp1);sort(ss+,ss+n+,cmp2); ;i<=n;i++) { int k=ss[i].bh; minx=h[k];maxx=minx+C/A; ,r=,sum=; ;j<=n;j++) { k=ss[j].bh; miny=s[k];ll now=C+A*minx+B*miny; ].x<=now)) { r++;int k=cc[r].bh; if((h[k]>=minx)&&(h[k]<=maxx))sum++; } ].xx<miny)) { l++;k=ss[l].bh; if((h[k]>=minx)&&(h[k]<=maxx))sum--; } ans=max(ans,sum); } } printf(; }