[NOIP 2011 提高组] 选择客栈

题意

有 n 家客栈排成一行，每家都有：

一个颜色 c_i
一个最低消费 b_i

要求选择两家不同的客栈给两位游客入住，满足：

两家客栈颜色相同
在这两家客栈之间，至少存在一家最低消费不超过 p 的咖啡店

问总共有多少种选择方案。

思路

先看一个最直接的小数据暴力：

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#include <bits/stdc++.h>
using namespace std;

const int MAXN = 205;

int n, k, p;
int color[MAXN], costv[MAXN];

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

    cin >> n >> k >> p;
    for (int i = 1; i <= n; i++) {
        cin >> color[i] >> costv[i];
    }

    // brute.cpp：小数据暴力解。
    // 直接枚举所有同色的住宿方案，再检查区间里有没有消费 <= p 的咖啡店。
    long long ans = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (color[i] != color[j]) {
                continue;
            }

            bool ok = false;
            for (int t = i; t <= j; t++) {
                if (costv[t] <= p) {
                    ok = true;
                    break;
                }
            }

            if (ok) {
                ans++;
            }
        }
    }

    cout << ans << '\n';

    return 0;
}

暴力做法是：

枚举两家客栈 (i,j)
要求它们颜色相同
再扫一遍区间 [i,j]，看有没有 b_t <= p

这个思路很好理解，但复杂度是 $O(n^2)$ 甚至更高，n=2*10^5 时肯定不行。

固定右端点来思考

假设当前把第 i 家客栈当作右端点。

那么一个左端点 j<i 合法，当且仅当：

color[j] = color[i]
区间 [j,i] 中存在某个位置 t，满足 b_t <= p

关键在第二条。

设我们从左到右扫描时，已经知道：

最近一次出现 b_t <= p 的位置在哪里

记这个位置叫 last_ok。

那么对于当前右端点 i：

如果某个左端点 j <= last_ok
那么区间 [j,i] 一定包含这个低消费位置，所以合法

反过来：

如果 j > last_ok
那么从 j 到 i 之间没有出现过消费不超过 p 的位置，所以不合法

于是问题变成：

对于当前颜色 c，前面有多少家颜色也是 c，并且位置不超过 last_ok？

如何在线统计？

维护两个数组：

total_cnt[c] 表示扫描到当前位置之前，颜色 c 总共出现了多少次
valid_cnt[c] 表示扫描到“最近一个低消费客栈位置”为止，颜色 c 出现了多少次

当遇到一个 b_i <= p 的位置时，说明从现在开始：

所有之前出现过的客栈
都已经落在新的 last_ok 左边

所以直接把：

valid_cnt[c] = total_cnt[c]

对所有颜色整体刷新一次即可。

之后当前客栈作为右端点时，能贡献的答案就是：

valid_cnt[color[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#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005;
const int MAXK = 55;

int n, k, p;
int color[MAXN], costv[MAXN];
long long total_cnt[MAXK]; // 到当前位置之前，每种颜色一共出现了多少次
long long valid_cnt[MAXK]; // 到最近一个低消费客栈位置为止，每种颜色出现了多少次

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

    cin >> n >> k >> p;
    for (int i = 1; i <= n; i++) {
        cin >> color[i] >> costv[i];
    }

    long long ans = 0;

    for (int i = 1; i <= n; i++) {
        int c = color[i];

        // 如果当前位置本身就是一个低消费客栈，
        // 那么对后面的所有位置来说，区间里已经保证能找到一个消费 <= p 的客栈。
        // 因此此时把“可作为左端点的数量”整体刷新为当前所有已出现客栈数。
        if (costv[i] <= p) {
            for (int col = 0; col < k; col++) {
                valid_cnt[col] = total_cnt[col];
            }
        }

        // 当前位置作为右端点时，能和多少个同色左端点配对，
        // 只取决于这些左端点是否在最近一个低消费客栈之前。
        ans += valid_cnt[c];

        total_cnt[c]++;

        // 如果当前位置本身低消费，那么它也能成为后面位置的合法左端点。
        if (costv[i] <= p) {
            valid_cnt[c]++;
        }
    }

    cout << ans << '\n';

    return 0;
}

复杂度

时间复杂度： $O(nk)$
空间复杂度： $O(k)$

其中 k<=50，所以这个复杂度完全可以通过。

总结

这题最关键的转化是：

对于固定右端点，区间是否合法，只取决于左端点是否在“最近一个低消费客栈”之前。

一旦想清这个性质，整题就从区间判定变成了一个按颜色做的线性统计问题。

[NOIP 2011 提高组] 选择客栈

目录

题意

思路

固定右端点来思考

如何在线统计？

代码

复杂度

总结