【排队买票】（C++代码）【卡特兰数】【反向求解】

1751 阅读 10 评论 0 点赞

##题目：
有M个小孩到公园玩，门票是1元。其中N个小孩带的钱为1元，K个小孩带的钱为2元。售票员没有零钱，问这些小孩共有多少种排队方法，使得售票员总能找得开零钱。注意：两个拿一元零钱的小孩，他们的位置互换，也算是一种新的排法。

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

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

$$K(n)=\frac{C(_{2n}^n)}{n+1}$$

当然，由于题目中说小孩交换位置算一种新的排队方式，所以还要再乘上 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）

![](/image_editor_upload/20191227091916_60824.png)

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

公式为：

$$\sum_{P=0}^KK(P)A{(_N^P)}A{(_K^P)}(K-P)R!$$

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

$$M!-\sum_{P=0}^KK(P)A{(_N^P)}A{(_K^P)}(K-P)R!$$

### 实现代码：
```cpp
#include<iostream>
using namespace std;

// 计算排列数
int a(int a1, int a2)
{
    if (a2 == 0)return 1;
    a2--;
    int pro = a1;
    for (int i = 0; i < a2; i++)
    {
        a1--;
        pro *= a1;
    }
    return pro;
}

// 计算组合数
int c(int c1, int c2)
{
    return a(c1, c2) / a(c2, c2);
}

// 计算卡特兰数
int catalan(int n)
{
    return c(2 * n, n) / (n + 1);
}

int main()
{
    int m, n, k;
    cin >> m >> n >> k;
    if (n < k)
        cout << 0;
    else
    {
        int sum = 0;
        for (int p = 0; p <= k; p++)
        {
            int r = m - 2 * p - 1;
            int nogood = catalan(p) * a(k, p) * a(n, p) * (k - p) * a(r, r);
            sum += nogood;
        }
        cout << a(m, m) - sum << endl;
    }
    return 0;
}

```

0.0分

11 人评分

本文分类：题解列表
浏览次数：1751 次浏览
发布日期：2019-12-27 09:19:43
本文链接：https://blog.dotcpp.com/a/64305

上一篇 > [编程入门]结构体之成绩统计2-题解(C++代码)
下一篇 > DNA-题解(C语言代码)，25行

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表共有 10 条评论

herobrine 3年前回复TA

@密码忘了 厉害

herobrine 3年前回复TA

@密码忘了 恒邦

herobrine 3年前回复TA

@密码忘了 非常好

herobrine 3年前回复TA

@密码忘了 没错

herobrine 3年前回复TA

希望以后多出这样的优质题解

DARLING·02 4年前回复TA

@DARLING·02 好吧，我发现我想错了

DARLING·02 4年前回复TA

@DARLING·02 如果M>N,那么当M=N做了排列后，后面的就都是M-N里面M的数，全是拿一块的小孩了，所以我们可以先让2N做一次排列，找到其中符合条件的，然后再做M-N的全排列

DARLING·02 4年前回复TA

爱你

是我呀 5年前回复TA

很棒

密码忘了 5年前回复TA

代码中并没有对 N = K 的情况给出一个单独的分支；
容易验证 N > K 时的公式也适用于 N = K 的情况；
另外 N < K 时显然是无解的。

【排队买票】 （C++代码）【卡特兰数】【反向求解】

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 10 条评论

发表评论 取消回复

【排队买票】（C++代码）【卡特兰数】【反向求解】

评论列表共有 10 条评论

发表评论取消回复