球迷购票问题

题意

有 n 个球迷拿着 50 元，另有 n 个球迷拿着 100 元。

每张票售价都是 50 元，售票员开始时没有零钱。

问这 2n 个人一共有多少种排队顺序，能够保证售票过程中始终不会出现“找不开钱”的情况。

思路

先看一个可以直接验证想法的朴素解：

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

using i64 = long long;

int n;
i64 ans;

// 直接枚举整条排队序列。
// fifty_left: 还剩多少个拿 50 元的人没排
// hundred_left: 还剩多少个拿 100 元的人没排
// change_cnt: 当前售票员手里有多少张 50 元零钱
void dfs(int fifty_left, int hundred_left, int change_cnt) {
    if (fifty_left == 0 && hundred_left == 0) {
        ans++;
        return;
    }

    if (fifty_left > 0) {
        dfs(fifty_left - 1, hundred_left, change_cnt + 1);
    }

    if (hundred_left > 0 && change_cnt > 0) {
        dfs(fifty_left, hundred_left - 1, change_cnt - 1);
    }
}

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

    cin >> n;
    dfs(n, n, 0);
    cout << ans << '\n';

    return 0;
}

这个暴力直接枚举整条队伍：

如果还有拿 50 元的人没排，就可以把他放到当前队尾
如果手里还有零钱，就可以把一个拿 100 元的人放到当前队尾

关键观察是：后续还能怎么排，只和下面两件事有关：

还剩多少个拿 50 元的人没排
还剩多少个拿 100 元的人没排

设 f(a,b) 表示还剩 a 个拿 50 元的人、b 个拿 100 元的人时，后面还能形成多少种合法方案。

状态表的含义

状态量	含义
`a`	还没排到的 `50` 元球迷人数
`b`	还没排到的 `100` 元球迷人数
`f(a,b)`	从当前状态出发的合法后续方案数

为什么只看 a,b 就够了？

因为当前已经排过的人数分别是：

拿 50 元的 n-a 个
拿 100 元的 n-b 个

所以当前手里的 50 元零钱张数就是：

(n-a) - (n-b) = b-a

于是转移很自然：

一定可以安排一个拿 50 元的人：f(a-1,b)
只有 b > a 时，当前零钱数才大于 0，可以安排一个拿 100 元的人：f(a,b-1)

边界：

a == 0 或 b == 0 时，后面只有一种排法

答案就是：

f(n,n)

这和合法括号序列、出栈序列计数是同一个 Catalan 数模型。

代码

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

using i64 = long long;

int n;
i64 memo[25][25];
bool vis[25][25];

// dfs(fifty_left, hundred_left) 表示：
// 还剩多少个拿 50 元的人、多少个拿 100 元的人没有排到时，
// 后面还能形成多少种合法排队方案。
i64 dfs(int fifty_left, int hundred_left) {
    if (fifty_left == 0 || hundred_left == 0) {
        return 1;
    }

    if (vis[fifty_left][hundred_left]) {
        return memo[fifty_left][hundred_left];
    }
    vis[fifty_left][hundred_left] = true;

    i64 ans = 0;

    // 安排一个拿 50 元的人，不需要找零。
    ans += dfs(fifty_left - 1, hundred_left);

    // 当前零钱数 = 已出现的 50 元人数 - 已出现的 100 元人数
    // = (n - fifty_left) - (n - hundred_left)
    // = hundred_left - fifty_left
    if (hundred_left > fifty_left) {
        ans += dfs(fifty_left, hundred_left - 1);
    }

    memo[fifty_left][hundred_left] = ans;
    return ans;
}

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

    cin >> n;
    cout << dfs(n, n) << '\n';

    return 0;
}

复杂度

状态数是 $O(n^2)$
每个状态最多两次转移
时间复杂度 $O(n^2)$
空间复杂度 $O(n^2)$

总结

这题最关键的不是“排队”本身，而是识别出这个前缀限制：

任意时刻，拿 50 元的人数都不能少于拿 100 元的人数

一旦把题目抽象成这个条件，它就和合法括号序列、出栈序列完全同构，自然落到 Catalan 数模型上。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

目录

题意

思路

状态表的含义

代码

复杂度

总结

一图流解析