BZOJ1071【SCOI2007】组队 <双指针>

Problem

【SCOI2007】组队

$\mathrm{Time\;Limit:\;3\;Sec}$
$\mathrm{Memory\;Limit:\;128\;MB}$

Description

$NBA$每年都有球员选秀环节。通常用速度和身高两项数据来衡量一个篮球运动员的基本素质。假如一支球队里速度最慢的球员速度为$min_V$，身高最矮的球员高度为$min_H$，那么这支球队的所有队员都应该满足：$A\times(height-min_H)+B\times(speed-min_V)\le C$。其中$A$和$B,C$为给定的经验值。这个式子很容易理解，如果一个球队的球员速度和身高差距太大，会造成配合的不协调。 请问作为球队管理层的你，在$N$名选秀球员中，最多能有多少名符合条件的候选球员。

Input

第一行四个数$N,A,B,C$。
下接$N$行每行两个数描述一个球员的$height$和$speed$。

Output

最多候选球员数目。

Sample Input

4 1 2 10
5 1
3 2
2 3
2 1

Sample Output

4

HINT

$N\le5000$，$height$和$speed$不大于$10000$。$A,B,C$在长整型以内。
$2016.3.26$数据加强，$\mathrm{Nano\_ape}$程序未重测。

标签：双指针

Solution

挺神的题，两个序列上双指针的操作挺奇葩。

对于每个队员，令$s=v+h$，将队员数组$A$同时复制到$B$中，分别排序。$A$按照$h$从小到大排序，$B$按照$s$从小到大排序。
首先按任意顺序枚举$v$的最小值大小，不妨直接再$A$中枚举。这时定义左指针和右指针$l$和$r$，只是与普通双指针不同的是，$l$指向的是$A$中的元素，$r$指向的是$B$中的元素，可以理解为$A$中的右指针是不动的，$B$中的左指针是不动的。这样精妙设计是考虑到$A$中递增的$h$值如果不满足要求，即小于枚举到的$H$值，小于的部分一定是从前面开始的；同样地，$B$中递增的$s$值如果不满足要求，即大于$A\times min_H+B\times min_V+C$，大于的部分一定是从后面开始的。这样对每个数组跑“单指针”即可得到可行最大子段，更新答案即可。

Code

#include <bits/stdc++.h>
#define MAX_N 5000
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n;    lnt A, B, C, miv, mxv;
struct node {lnt h, v, s;} p[MAX_N+5], q[MAX_N+5];
bool cmph(const node &a, const node &b) {return a.h <= b.h;}
bool cmps(const node &a, const node &b) {return a.s <= b.s;}
int main() {
    read(n), read(A), read(B), read(C);	int ans = 0;
    for (int i = 1; i <= n; i++) read(p[i].h), read(p[i].v);
    for (int i = 1; i <= n; i++) p[i].s = A*p[i].h+B*p[i].v, q[i] = p[i];
    sort(p+1, p+n+1, cmph), sort(q+1, q+n+1, cmps);
    for (int i = 1, l, r, cnt; i <= n; i++) {
        l = r = cnt = 0, miv = p[i].v, mxv = miv+C/B;
        for (int j = 1; j <= n; j++, ans = max(ans, cnt)) {
            while (r < n && q[r+1].s <= A*p[j].h+B*p[i].v+C)
                r++, cnt += q[r].v >= miv && q[r].v <= mxv;
            while (l < n && p[l+1].h < p[j].h)
                l++, cnt -= p[l].v >= miv && p[l].v <= mxv;
        }
    }
    return printf("%d\n", ans), 0;
}