[USACO13NOV] Crowded Cows S

题意

有 n 头牛，每头牛有：

一个位置 x_i
一个高度 h_i

如果一头牛满足：

左边距离不超过 D 的范围内，存在一头牛，高度至少是它的两倍；
右边距离不超过 D 的范围内，也存在一头牛，高度至少是它的两倍；

那么它就被称为 “crowded”。

要求统计这样的牛有多少头。

思路

先看一个最直接的暴力程序：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60#include <bits/stdc++.h>
using namespace std;

const int MAXN = 205;

struct Cow {
    int x, h;
};

int n, d;
Cow cow[MAXN];

bool cmp_by_x(const Cow &a, const Cow &b) {
    return a.x < b.x;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> d;
    for (int i = 1; i <= n; i++) {
        cin >> cow[i].x >> cow[i].h;
    }

    sort(cow + 1, cow + n + 1, cmp_by_x);

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        bool has_left = false;
        bool has_right = false;

        for (int j = i - 1; j >= 1; j--) {
            if (cow[i].x - cow[j].x > d) {
                break;
            }
            if ((long long)cow[j].h >= 2LL * cow[i].h) {
                has_left = true;
                break;
            }
        }

        for (int j = i + 1; j <= n; j++) {
            if (cow[j].x - cow[i].x > d) {
                break;
            }
            if ((long long)cow[j].h >= 2LL * cow[i].h) {
                has_right = true;
                break;
            }
        }

        if (has_left && has_right) {
            ans++;
        }
    }

    cout << ans << '\n';
    return 0;
}

暴力做法先按位置排序，然后对每头牛：

向左扫到距离超过 D 为止；
向右再扫一次；
检查是否都能找到高度至少两倍的牛。

这个做法很好理解，也适合对拍，但最坏复杂度会到 $O(n^2)$ 。

先把题目转成“窗口最大值”

对一头牛 i，题目真正关心的并不是左右窗口里的所有牛，而只是：

左边距离不超过 D 的牛里，最高的是多少；
右边距离不超过 D 的牛里，最高的是多少。

因为：

如果这一侧的最高牛都不够 2*h_i，那别的牛更不可能够；
如果最高牛已经够了，那这一侧条件就已经满足。

所以问题可以改写成：

求每头牛左侧窗口最大高度；
求每头牛右侧窗口最大高度。

为什么适合单调队列

把所有牛按位置升序排序后，随着我们从左到右扫描：

左侧距离不超过 D 的窗口会不断右移；
有些旧牛会因为离得太远而出窗口；
当前牛会作为新元素进入后面的窗口。

这正是滑动窗口最大值的标准模型。

第一遍：求左侧最大高度

从左到右扫描，用一个单调队列维护当前牛左侧窗口中的候选牛下标。

维护规则：

队首如果已经离当前牛超过 D，就弹掉；
此时队首就是窗口最大高度；
当前牛入队前，把队尾所有高度不超过它的牛弹掉，保持高度单调递减。

这样每头牛的 left_max_h[i] 都能在线性时间内求出。

第二遍：求右侧最大高度

完全对称，从右往左再做一次即可。

最终判断

如果一头牛同时满足：

left_max_h[i] >= 2 * h_i
right_max_h[i] >= 2 * h_i

那它就是拥挤牛，计入答案。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91#include <bits/stdc++.h>
using namespace std;

const int MAXN = 50005;

struct Cow {
    int x, h;
};

int n, d;
Cow cow[MAXN];
int left_max_h[MAXN];
int right_max_h[MAXN];

bool cmp_by_x(const Cow &a, const Cow &b) {
    return a.x < b.x;
}

void calc_left_max() {
    deque<int> q;

    for (int i = 1; i <= n; i++) {
        // 删除左侧距离超过 D 的牛，它们已经不在窗口里了。
        while (!q.empty() && cow[i].x - cow[q.front()].x > d) {
            q.pop_front();
        }

        if (q.empty()) {
            left_max_h[i] = 0;
        }
        else {
            left_max_h[i] = cow[q.front()].h;
        }

        // 把当前牛加入单调队列，维护窗口内高度最大值。
        while (!q.empty() && cow[q.back()].h <= cow[i].h) {
            q.pop_back();
        }
        q.push_back(i);
    }
}

void calc_right_max() {
    deque<int> q;

    for (int i = n; i >= 1; i--) {
        // 删除右侧距离超过 D 的牛。
        while (!q.empty() && cow[q.front()].x - cow[i].x > d) {
            q.pop_front();
        }

        if (q.empty()) {
            right_max_h[i] = 0;
        }
        else {
            right_max_h[i] = cow[q.front()].h;
        }

        while (!q.empty() && cow[q.back()].h <= cow[i].h) {
            q.pop_back();
        }
        q.push_back(i);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> d;
    for (int i = 1; i <= n; i++) {
        cin >> cow[i].x >> cow[i].h;
    }

    sort(cow + 1, cow + n + 1, cmp_by_x);

    calc_left_max();
    calc_right_max();

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        // 一头牛拥挤，当且仅当左右两边都存在一头高度至少是它两倍的牛。
        if ((long long)left_max_h[i] >= 2LL * cow[i].h &&
            (long long)right_max_h[i] >= 2LL * cow[i].h) {
            ans++;
        }
    }

    cout << ans << '\n';
    return 0;
}

复杂度

时间复杂度： $O(n log n)$
其中排序是 $O(n log n)$ ，两次单调队列扫描是 $O(n)$ 。
空间复杂度： $O(n)$

总结

这题的关键不是直接找“是否存在一头足够高的牛”，而是先意识到：

每一侧只需要知道最大高度。

一旦想到这一点，题目就会自然转化成两个滑动窗口最大值问题。
排序后做两遍单调队列扫描，就是标准解法。