题目描述
有M个小孩到公园玩，门票是1元。其中N个小孩带的钱为1元，K个小孩带的钱为2元。售票员没有零钱，问这些小孩共有多少种排队方法，使得售票员总能找得开零钱。注意：两个拿一元零钱的小孩，他们的位置互换，也算是一种新的排法。（M<=10）
输入格式
输入一行，M,N,K(其中M=N+K,M<=10).
输出格式
输出一行，总的排队方案。
样例输入
4 2 2
样例输出
8
方法一：
题目分析:
由题目可知，必须满足条件N>=K,拆分这个条件：
N=K
N个小孩带的钱为1元，另外N个小孩带的钱为2元，即2N=M，可以直接用卡特兰数：
由于题目中说小孩交换位置算一种新的排队方式，所以还要再乘上 n 的全排列（乘两遍：N个小孩带的钱为1元，另外N个小孩带的钱为2元），即
N>K
先将非法的排列方法筛选出来，再用总的排列方法-非法的排列方法，得最终排列的方法数：
总的排列方法：
因为由M人，所以总的排列方法有M！种
非法的排列可以将其分为三个部分：
- 前 2P 个小孩
- 第 2P + 1 个小孩
- 剩下的小孩，假设共 R 个（R = M - 2P - 1）
第一部分可以使用卡特兰公式进行运算，即,其中p在0~k范围内，但不能为K，因为第二部分必须为K中的一部分
其次，p可以为0，因为第二部分2p+1为持有2元的小孩，即第一个排队的人就是持有2元的小孩，也是非法的排列顺序：
由于第一部分已经用了k中的p个，第二部分有k-p个选择:
K-P
第三部分随意排列，即r=m-2*p-1进行随意排列：
R！
所以合法的排列公式为：
用代码实现即：
long long sum = 0; for (int p = 0; p <k; p++) { int r = m - 2 * p - 1; long long fail = catalan(p) * rank(k, p) * rank(n, p) * (k - p) * rank(r, r); sum += fail; } long long result = rank(m, m) - sum; printf("%lld\n", result);
所以完整的代码得，如果其中有一些小漏洞，请大佬们不吝赐教！💖💖
#include<stdio.h> // 求排列数 long long rank(int a1, int a2) { if (a2 == 0) return 1; a2--;//这里一定不能忘记，因为要排除rank(c1,c2)中,c1为0得情况 long long pro = a1; for (int i = 0; i < a2; i++) { a1--; pro *= a1; } return pro; } // 求组合数 long long comb(int c1, int c2) { return rank(c1, c2) / rank(c2, c2); } // 求卡特兰数 long long catalan(int n) { return comb(2 * n, n) / (n + 1); } int main() { int m, n, k; scanf("%d %d %d", &m, &n, &k); if (n < k) { printf("Error: n must be greater than or equal to k.\n"); return 0; } else { long long sum = 0; for (int p = 0; p <k; p++) { int r = m - 2 * p - 1; long long fail = catalan(p) * rank(k, p) * rank(n, p) * (k - p) * rank(r, r); sum += fail; } long long result = rank(m, m) - sum; printf("%lld\n", result); } return 0; }
方法二
我在网上也看到一种更简便得方法,在这里分享给大家，我的理解如下：
他利用了数据结构中的next_permutation(a,a+N)方法进行全排列，不熟悉的可以看这篇文章：
我们可以把它理解为序列的字典序的前后，严格来讲，就是对于当前序列pn，他的下一个序列pn+1满足：不存在另外的序列pm，使pn<pm<pn+1
正确的排列方法为：每个2前面至少对应着一个1
用一个num记录，num如果有1就++，有2就- - ，如果过程中num<0则证明存在有一个2没有一个1对应。
代码为：
这里初始前面的1为0~K-1，后面的2为K~N-1 所以小于K的就相当于是1了，大于K的就相当于是2了，为了方便使用next_permutation()
for (int i=0; i<K; i++) { a[i] = i; } for (int i=K; i<N; i++) { a[i] = i; } do { int flag = 0; // check每个全排列， num务必要初始化 int num = 0; for (int i=0; i<N; i++) { if (a[i] >= K) { num--; } else { num++; } if (num < 0) { flag = 1; break; } } if (flag == 0) { // for (int i=0; i<N; i++) { // cout << a[i]; // } // cout << "\n"; res++; }
这还不够，需要判断类似1122的所有全排列包括重复的，因为初始前面的1为0~K-1，后面的2为K~N-1 ，对于0123的序列我们可以直接使用next_permutation()，完整代码如下：
#include <iostream> #include <algorithm> using namespace std; int N, K, M; int main() { while (cin >> N >> K >> M) { int a[N], res = 0; for (int i=0; i<K; i++) { a[i] = i; } for (int i=K; i<N; i++) { a[i] = i; } do { int flag = 0; // check每个全排列， num务必要初始化 int num = 0; for (int i=0; i<N; i++) { if (a[i] >= K) { num--; } else { num++; } if (num < 0) { flag = 1; break; } } if (flag == 0) { // for (int i=0; i<N; i++) { // cout << a[i]; // } // cout << "\n"; res++; } } while (next_permutation(a,a+N)); cout << res << "\n"; } return 0; }
