全排列解决排队买票

解题思路：

由题目可知，1元小孩通过，售票员手里的零钱+1，2元的小孩通过，售票员的零钱-1，初始的零钱数目是0。

不妨把1元的小孩设成1，把2元的小孩设成-1，建立一个由n个1和k个-1组成的m元动态数组，将数组全排列，将每种情况的数组从头累加，累加过程中结果若和<0，则此种排列方式不成立，如果累加到最后和一直非负，则排列方法有效。计算有效排列方式个数并输出。

注意事项:如果2元小孩数量比1元小孩多，那么不可能成立

参考代码:

#include <stdio.h>

#include <stdlib.h>

int route = 0;

int main()

{

int* a;

int m, n, k;/*n个小孩1，k个小孩2*/

scanf("%d%d%d", &m, &n, &k);

a = (int*)calloc(m, sizeof(int));

for (int i = 0; i < m; i++)

{

a[i] = -1;

}

for (int i2 = 0; i2 < n; i2++)

{

a[i2] = 1;

}

perm(a, 0, m - 1);

printf("%d", route);

}

int perm(int a[], int begin, int n)/*n是数组最后一个数的角标*/

{

if (begin == n)

{

int sum = 0;

int count = 0;

for (int i = 0; i <= n; i++)

{

sum = sum + a[i];

if (sum < 0)

{

break;

}

else

{

count++;

}

}

if (count == n + 1)

{

route++;

}

}

else

{

for (int k = begin; k <= n; k++)

{

swap(a, begin, k);

perm(a, begin + 1, n);

swap(a, begin, k);

}

}

}

int swap(int arr[], int a, int b)/*数组中arr[a]和arr[b]交换顺序*/

{

int temp = arr[a];

arr[a] = arr[b];

arr[b] = temp;

}