自动搬运

查看原文

来自洛谷，原作者为

	DDOSvoid **

搬运于2025-08-24 21:57:13，当前版本为作者最后更新于2018-09-21 18:53:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

令 $H$ 代表 $minh$，$V$ 代表 $minv$

考虑满足条件的队员应满足 3 个条件：

1. $A*h+B*v\le C+A*H+B*V$
2. $h\ge H$
3. $v\ge V$

考虑如果满足 1 和 3，则能得出 4. $h \le \frac{C}{A}+H$

但是根据 1 和 4 或 3 和 4，却不能推出 3 或 1，所以这段好像没啥用？

令 $s$ 表示 $A*h+B*v$

考虑外层枚举 $H$，内层枚举 $V$，将数组按照 $s$ 排序，那么满足第一个条件的位置会随着内层的枚举递增。

当然只有第一个条件是不够的，考虑如何增加其他的条件，因为外层枚举是固定的，所以显然可以在统计的答案的时候遵守限制 2。考虑满足第三个限制。如果只是简单的满足的话（如下

for(int i = 1; i <= n; ++i){ // H
        int r = 0, cnt = 0;
		for(int j = 1; j <= n; ++j){ // V
        	while(r < n && a3[r + 1].s <= A * a1[i].h + B * a2[j].v)
        		++r, cnt += (a3[r].h >= a1[i].h && a3[r].v >= a2[j].v);
        	// del 
		}
    }

那么随着 j 的增加，我们的删除是 $O(n)$

考虑如何做到 $O(1)$ 的删除，考虑刚才推出的性质 4，如果满足 1 和 4 的话，的确没法推出 $v\ge V$，但是如果性质 4（$h \le \frac{C}{A}+H$ 存在的话，假设此时 $v<V$ 那么，我们能得到 $A*h+B*v\le A*H+B*V+C$

这有什么用呢？考虑在统计的时候并不一定满足性质 1、2、3 的答案，而是只满足 1 和 2 还有 4 的答案，然后再将多余的减掉，我们发现减的过程是单调的（如下

for(int i = 1; i <= n; ++i){ // h
        int l1 = 0, l2 = 0, cnt = 0;
        int Min = a1[i].h, Max = a1[i].h + C / A;	
        for(int j = 1; j <= n; ++j){ // v
            while(l2 < n && a3[l2 + 1].s <= C + A * a1[i].h + B * a2[j].v)
                ++l2, cnt += (a3[l2].h >= Min && a3[l2].h <= Max);
            while(l1 < n && a2[l1 + 1].v < a2[j].v)
                ++l1, cnt -= (a2[l1].h >= Min && a2[l1].h <= Max);	
            ans = max(ans, cnt);
        }
    }

可以发现这样是对的。另外，再删除过程中是不会删除没加入的点的。

证明如下：

首先，它被删除了，说明他满足不等式 $a2[l1].h >= Min$ 和 $a2[l1].h <= Max$，即 $A*h\le A*H+C$ 且 $h\ge H$。我们知道他没有被添加，说明 $A*h+B*v>A*H+B*V+C$，解得 $v>V$，但 $a2[l1 + 1].v < a2[j].v$

并且也不会漏删加入的点（这个非常显然

并且在固定 i 和 j 之后，应该要被删除的点一定会在这次被删除，

分两种情况讨论：

1 应该删除的点在之后才被删除

证明：首先，它在这次被加入了，说明 $A*h+B*v\le C+A*H+B*V$，并且 $h \le \frac{C}{A}+H$。它应该被删除，说明 $v<V$，那么肯定会在现在被删除

2 应该删除的点在之前被删除了

证明：它被删除了，说明 $h \le \frac{C}{A}+H$，且 $v<V$，这个 $V$ 是当时枚举的，那么在当时就有 $A*h+B*v\le C+A*H+B*V$，所以在当时就会被加入

所以删除满足单调性，所以，应该就没了。贴一下 AC 代码。

如有不严谨的地方，请指出

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 5010
using namespace std;

int A, B, C, n, m;

struct node{
    int h, v, s;	
}a1[maxn], a2[maxn], a3[maxn];

inline bool cmp1(node x, node y){return x.h < y.h;}
inline bool cmp2(node x, node y){return x.v < y.v;}
inline bool cmp3(node x, node y){return x.s < y.s;}

int ans;
int main(){
    scanf("%d%d%d%d", &n, &A, &B, &C);
    for(int i = 1; i <= n; ++i){
        scanf("%d%d", &a1[i].h, &a1[i].v);
        a1[i].s = A * a1[i].h + B * a1[i].v;
        a3[i] = a2[i] = a1[i];
    }
    //sort(a1 + 1, a1 + n + 1, cmp1); 
    sort(a2 + 1, a2 + n + 1, cmp2);
    sort(a3 + 1, a3 + n + 1, cmp3);
    for(int i = 1; i <= n; ++i){ // h
        int l1 = 0, l2 = 0, cnt = 0;
        int Min = a1[i].h, Max = a1[i].h + C / A;	
        for(int j = 1; j <= n; ++j){ // v
            while(l2 < n && a3[l2 + 1].s <= C + A * a1[i].h + B * a2[j].v)
                ++l2, cnt += (a3[l2].h >= Min && a3[l2].h <= Max);
            while(l1 < n && a2[l1 + 1].v < a2[j].v)
                ++l1, cnt -= (a2[l1].h >= Min && a2[l1].h <= Max);	
            ans = max(ans, cnt);
        }
    }
    cout << ans;
    return 0; 
}