「优质题解」排队买票

这道题的地址，想尝试的小伙伴可以来试哦：

https://www.dotcpp.com/oj/problem1163.html

思路：

1. N = K

考虑当 N = K 时的特殊情况，即有 2N 个小孩，其中N个小孩带的钱为1元，另外N个小孩带的钱为2元。

此时可利用卡特兰数的通项公式简单求解:

当然，由于题目中说小孩交换位置算一种新的排队方式，所以还要再乘上 n 的全排列（乘两遍）。

2. N > K

当 N > K 时，无法直接用卡特兰数求解，这时我们可以换一种思维：无法直接求出合法的排队方式数，那就先求出非法的排队方式数，再用总的排队方式数减去，即得合法的排队方式数：

总的排队方式数：

很简单：一共 M 人排队，有 M！（M 的全排列）种排队方式。

非法的排队方式数：

我们考虑一下非法的排队方式有什么特征：

• （1） 前 2P 个小孩组成一个合法的排队，且持有 1 元的小孩和持有 2 元的小孩数量相等，皆为 P。（P = 0, 1, 2……）
• （2） 第 2P + 1 个小孩持有 2 元。

证明：

• （1） 证明满足此特征的排队均非法： 显然，由于前 2P 个小孩使得售票员“收支平衡”，第 2P + 1 个小孩到来时刚好无钱可找，所以是非法的排队。
• （2） 证明非法的排队均满足此特征：
  • 当非法队伍长度为奇数时： <a> 如果除去最后一个孩子仍是非法排队： 去掉队尾一个小孩，进行队伍长度为偶数时的论证。 <b> 如果除去最后一个孩子变为合法排队： ※ 则最后一个孩子一定持有 2 元。（一个合法排队加上一个持有 1 元的小孩并不会变成非法排队） ※ 此合法队列中持有 1 元的小孩和持有 2 元的小孩数量相等。（若持有 2 元的小孩数量较多，此队列一定是非法队列；若持有 1 元的小孩较多，则即便最后一个小孩持有 2 元也不会变为非法队列）
  • 当非法队伍长度为偶数时： 则总是存在这样一个正整数 Q（2Q <= 队列长度），使得前 2Q 个小孩构成一非法排队（换言之，如果对于任意的正整数 Q，总有：前 2Q 个小孩构成的队列是合法的，那么这个队列本身也是合法的。） 于是可以对前 2Q 个小孩的非法队列进行递归论证，直到找不到这样的 Q 时，去除队尾一个小孩，进行奇数队伍论证。

计算公式：

非法排队特征：

（1） 前 2P 个小孩组成一个合法的排队，且持有 1 元的小孩和持有 2 元的小孩数量相等，皆为 P。（P = 0, 1, 2……）

（2） 第 2P + 1 个小孩持有 2 元。

于是我们可以把非法排队分为 3 部分：

• 前 2P 个小孩
• 第 2P + 1 个小孩
• 剩下的小孩，假设共 R 个（R = M - 2P - 1）

前 2P 个小孩组成一个合法排队，且满足：M’ = 2P，N’ = K’ = P。 于是排队数可以用卡特兰数计算。 第 2P + 1 个小孩要持有 2 元，由于前 2P 个小孩中已经用掉 P 个持有 2 元的小孩，此处还有 K - P 种选择。 最后 R 个小孩的排队方式不影响整体性质，所以全排列。

公式为：

合法的排队方式数：

合法的排队方法数就等于总的方法数减去非法的方法数：

代码实现：