「優質題解」排隊買票

2020 年 1 月 3 日
筆記

這道題的地址，想嘗試的小夥伴可以來試哦：

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 個小孩的排隊方式不影響整體性質，所以全排列。

公式為：

合法的排隊方式數：

合法的排隊方法數就等於總的方法數減去非法的方法數：