Sengxian's Blog

题目地址

描述

NBA 每年都有球员选秀环节。通常用速度和身高两项数据来衡量一个篮球运动员的基本素质。假如一支球队里速度最慢的球员速度为 $\mathrm{minV}$，身高最矮的球员高度为 $\mathrm{minH}$，那么这支球队的所有队员都应该满足:

其中 $A$ 和 $B$，$C$ 为给定的经验值。这个式子很容易理解，如果一个球队的球员速度和身高差距太大，会造成配合的不协调。请问作为球队管理层的你，在 $n(n\le 5000)$ 名选秀球员中，最多能有多少名符合条件的候选球员。

分析

这一种涉及到最大值，最小值的问题，通常的方法是枚举，如果满足二分三分性质，可以二分三分。而如果不满足，要么这个题是个水题，要么这个题有单调性。

不等式的原始形式是比较烦人的，我们考虑拆开：

我们设 $s = A \cdot \mathrm{height} + B \cdot \mathrm{speed}$。

最暴力的方法是枚举 $\mathrm{minV}$ 和 $\mathrm{minH}$，然后在这个情况下判断有多少个球员能加入，复杂度为 $O(n^3)$。

我们考虑枚举一维，不妨枚举 $\mathrm{minV}$，则我们忽略所有速度小于 $\mathrm{minV}$ 的人，这一点后面不再强调。

我们接着枚举 $\mathrm{minH}$，我们发现，如果将人按照 $\mathrm{height}$ 排序的话，$s = A \cdot \mathrm{height} + B \cdot \mathrm{speed}$ 不满足单调递增，没有办法使用滑动窗口（也称双指针）。换句话说，每次可行的范围不是一个完整的区间。

如果你不会滑动窗口也无所谓，直接看就行了。

非常好的一点是，随着 $\mathrm{minH}$ 的增加，不等式右边 $C + A\cdot\mathrm{minH} + B\cdot\mathrm{minV}$ 也增加。我们维护两个序列，第一个序列按照 $s$ 从小到大排序，第二个序列按照 $\mathrm{height}$ 从小到大排序，我们从小到大枚举 $\mathrm{minH}$。

枚举 $\mathrm{minH}$ 的过程中记录两个指针，第一个指针为 $r$，表示第一个序列 $[0, r)$ 中的所有人满足不等式的限制（显然 $r$ 单调不减）。第二个指针为 $l$，表示第二个序列中 $[0, l)$ 中所有人满足 $\mathrm{height} < \mathrm{minH}$（显然 $l$ 也单调不减）。每次枚举到新的 $\mathrm{minH}$ 我们要做的事情，就是通过 $r$ 指针的增加，来加入满足不等式的人，通过 $l$ 指针的增加，来删除满足不等式但是却不满足身高小于 $\mathrm{minH}$ 的人。

我们看当枚举到新的 $\mathrm{minH}$ 时，怎么维护这两个指针。对于 $r$，如果第一个序列第 $r$ 个人满足不等式，并且身高大于等于第一个序列第 $l$ 个人的身高，那么我们加入这个人，答案 +1。为什么要这样？因为如果这个人的身高小于第一个序列第 $l$ 个人的身高，他本来就不满足 $\mathrm{minH}$ 的限制条件，而且我们在之前 $l$ 的增加过程中遍历过这个人却没有删这个人，所以我们不能加入这个人（他以后也不会被删除）。而大于等于第一个序列第 $l$ 个人的身高的人，接下来 $l$ 增加的过程中，是可以被删的，所以我们加入他也无妨。

接下了维护 $l$，很简单，如果满足 $\mathrm{height} < \mathrm{minH}$ 而且满足不等式，就将其删掉，答案 -1。

显然，我们每次都考虑了所有满足不等式的人，而且不满足 $\mathrm{height}\ge\mathrm{minH}$ 的人都被删除，所以是正确的。

由于每次指针的单调的变化，维护了一段区间，所以我们形象的叫这种方法为“滑动窗口”。

本题之所以可以使用滑动窗口的原因，归根到底还是因为，在 $\mathrm{minH}$ 增加的过程中，不等式的限制是放的越来越宽的，这样，我们才可以保证“之前满足不等式的点，现在仍然满足不等式”，以及“被删掉的人不会再次加入”这两个性质，从而降低了复杂度。

代码

//  Created by Sengxian on 09/05/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 1071 双滑动窗口
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int ReadInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}

const int maxn = 5000 + 3;
ll A, B, C;
int n;

struct data {
    int h, v;
    ll s;
}datas[2][maxn];

inline bool cmp_s(const data &lhs, const data &rhs) {
    return lhs.s < rhs.s;
}

inline bool cmp_h(const data &lhs, const data &rhs) {
    return lhs.h < rhs.h;
}

int solve(int min_v) {
    int l = 0, r = 0, ans = 0, sum = 0, min_h = 0;
    ll val = 0;
    for (int i = 0; i < n; ++i) {
        //enumerate h
        min_h = datas[1][i].h;
        val = C + min_h * A + min_v * B;
        while (r < n && datas[0][r].s <= val) {
            sum += datas[0][r].v >= min_v && datas[0][r].h >= datas[1][l].h;
            r++;
        }
        while (l < n && datas[1][l].h < min_h) sum -= datas[1][l].s <= val && datas[1][l].v >= min_v, ++l;
        ans = max(ans, sum);
    }
    return ans;
}

int main() {
#ifndef ONLINE_JUDGE
//    freopen("test.in", "r", stdin);
#endif
    n = ReadInt(), A = ReadInt(), B = ReadInt(), C = ReadInt();
    for (int i = 0; i < n; ++i) {
        datas[0][i].h = ReadInt(), datas[0][i].v = ReadInt();
        datas[0][i].s = datas[0][i].h * A + datas[0][i].v * B;
        datas[1][i] = datas[0][i];
    }
    sort(datas[0], datas[0] + n, cmp_s);
    sort(datas[1], datas[1] + n, cmp_h);
    int ans = 0;
    for (int i = 0; i < n; ++i) ans = max(ans, solve(datas[0][i].v));
    printf("%d\n", ans);
    return 0;
}