【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;

}