题目描述
有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; }