【BZOJ1071】[SCOI2007]组队(神仙题)

【BZOJ1071】[SCOI2007]组队(神仙题)

题面

BZOJ

洛谷

题解

首先把式子整理一下,也就是\(A*h+B*v\le C+A*minH+B*minV\)

我们正常能够想到的做法是钦定一个\(minH\)然后怎么暴力。然而发现并不行,因为\(minV\)就不单调了。那么如果要暴力只能同时枚举两个\(min\)了,显然如果我们枚举完之后,按照\(A*h+B*v\)排序,满足条件的显然就是单调的了,我们把这个值叫做\(s\)。看起来很美好,然而我们忽略了一个限制条件,也就是\(h\ge minH,v\ge minV\),如果用数据结构维护显然\(GG\),前面暴力枚举已经\(O(n^2)\)了,再多个\(log\)基本凉了。

我们假装外层枚举了最小的\(minV\),按照\(h,s\)两个值分别排序。那么显然这两个满足条件的都是一段区间,考虑\(v\)的可行范围,首先\(v\ge minV\),然后假装\(h=minH\),则\(v\le minV+\frac{C}{B}\)。然后我们再把区间内所有不满足\(h\le minH\)的全部减去,似乎就是答案了。

具体的原因?我也不会,那就假装是对的吧。可以戳这里看看。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define MAX 5050
int n,A,B,C,ans,minV,mx;
struct Node{int h,v,s;void calc(){s=A*h+B*v;}}p[2][MAX];
bool cmpH(Node a,Node b){return a.h<b.h;}
bool cmpS(Node a,Node b){return a.s<b.s;}
bool check(int i,int x){return p[i][x].v<=mx&&p[i][x].v>=minV;}
int main()
{
scanf("%d%d%d%d",&n,&A,&B,&C);
for(int i=1;i<=n;++i)
{
scanf("%d%d",&p[0][i].h,&p[0][i].v);
p[0][i].calc();p[1][i]=p[0][i];
}
sort(&p[0][1],&p[0][n+1],cmpH);
sort(&p[1][1],&p[1][n+1],cmpS);
for(int i=1;i<=n;++i)
{
minV=p[0][i].v,mx=minV+C/B;
int l=0,r=0,cnt=0;
for(int j=1;j<=n;++j)
{
while(r<n&&p[1][r+1].s-A*p[0][j].h-B*p[0][i].v<=C)cnt+=check(1,++r);
while(l<n&&p[0][l+1].h<p[0][j].h)cnt-=check(0,++l);
ans=max(ans,cnt);
}
}
printf("%d\n",ans);return 0;
}
上一篇:BZOJ 1071 [SCOI2007]组队


下一篇:BZOJ1071 [SCOI2007]压缩 其他