Manchester-【排队买票】(全排列，两种思路，优化后快近10倍，简单易懂）

解题思路:

思路一（优化前）
1.整个问题，当做售票员起初没有钱，然后孩子们的钱的面额为1 元，和2元，票价一元，问这些小孩共有多少种排队方法，使所有孩子买到票；
2.把孩子们的钱，放入数组A[]中，如题目两个一元，两个两元就是A[0]=1;  A[1]=1;  A[2]=2;  A[3]=2;

实现算法
void format(int *A,int N,int K)
{

  for(int i=0;i<(N+K);i++)
  {
    if(i<N)
    A[i]=1;
    else
    A[i]=2;
  }
    
  return;
}

3.把A[]进行全排列，每一种排列方式，判断一下，是否可以所有孩子都可以买到票；

4.判断方法，把售票员起初的钱 int num_of_yiyuan=0，设为0，遍历A[],当A[i]等于1时，num_of_yiyuan++，表示售票员有的

一元纸币的数目加1，当A[i]等于2时，要补钱，所以num_of_yiyuan--，表示售票员有的一元纸币数目减1；当num_of_yiyuan

为负数时，说明这种排队方式没办全买到票，就跳出循环；若循环正常结束，则num_of_yiyuan大于等于0，能全部买到票，满足的排队情况数目（sum）加1；

void panduan(int *A,int M,int *sum)
{
  int num_of_yiyuan=0;

  for(int i=0;i<M;i++)
   {
     if(A[i]==1)
      num_of_yiyuan++;
      else
      num_of_yiyuan--;

      if(num_of_yiyuan<0)
       break;
   }
  if(num_of_yiyuan>=0)
   (*sum)++;
return ;
}

 5.把判断函数加在全排列函数中即可

void pailie(int *A,int index,int length,int *sum)
{

   int i=0,j=0;

   if(index==length)
    {
     panduan(A,length,sum);
    }
    else
     for(j = index;j < length; j++)
        {
            swap(&A[j],&A[index]);
            pailie(A,index+1,length,sum);
            swap(&A[j],&A[index]);
        }
return ;
}

参考代码:

#include<stdio.h>
#include<malloc.h>
void format(int *A,int N,int K);  //把每个孩子的钱存入A[]
void pailie(int *A,int index,int length,int *sum);   //全排列函数
void swap(int *x,int *y);                          //用于全排列中交换两个数
void panduan(int *A,int M,int *sum);             //判断排队方式是否满足条件
int main()
{

 int M,N,K,sum=0;  //sum用于记录满足条件的排队情况数
 int *A;
 while( scanf("%d%d%d",&M,&N,&K)!=EOF)
 {
    sum=0;               //每次新数据置0
    A=(int *)malloc(M*sizeof(int));
    format(A,N,K);
    pailie(A,0,M,&sum);
    printf("%d\n",sum);
 }
return 0;
}

/*===================================================*/
void format(int *A,int N,int K)
{

  for(int i=0;i<(N+K);i++)
  {
    if(i<N)
    A[i]=1;
    else
    A[i]=2;
  }
    
  return;
}
/*===================================================*/
void pailie(int *A,int index,int length,int *sum)
{

   int i=0,j=0;

   if(index==length)
    {
     panduan(A,length,sum);
    }
    else
     for(j = index;j < length; j++)
        {
            swap(&A[j],&A[index]);
            pailie(A,index+1,length,sum);
            swap(&A[j],&A[index]);
        }
return ;
}

/*===================================================*/
void swap(int *x,int *y)
{
  int z=(*x);
  (*x)=(*y);
  (*y)=z;
return ;
}
/*===================================================*/
void panduan(int *A,int M,int *sum)
{
  int num_of_yiyuan=0;

  for(int i=0;i<M;i++)
   {
     if(A[i]==1)
      num_of_yiyuan++;
      else
      num_of_yiyuan--;

      if(num_of_yiyuan<0)
       break;
   }
  if(num_of_yiyuan>=0)
   (*sum)++;
return ;
}

下面进行代码优化优化后时间从327 变为 38；

思路2（优化）

分析整个问题发现，第一个小孩的纸币面额必须要是1元，排队方式才有可能成立，所以，原问题变成M-1个人的全排列，又根据，两个拿一元零钱的小孩，他们的位置互换，也算是一种新的排法，所以我们把第一个拿一元钱的小孩分离出来，让剩下的小孩做排列，判断它们是否满足条件，最后把剩下小孩所做的排列所满足条件的数目乘以拿一元钱小孩的人数，就是成立的排队数；

注意：该思路售票员初始拥有的钱 int num_of_yiyuan=1为1；

#include<stdio.h>
#include<malloc.h>
void format(int *A,int N,int K);
void pailie(int *A,int index,int length,int *sum);
void swap(int *x,int *y);
void panduan(int *A,int M,int *sum);
int main()
{

 int M,N,K,sum=0;
 int *A;
 while( scanf("%d%d%d",&M,&N,&K)!=EOF)
 {
    sum=0;
    A=(int *)malloc((M-1)*sizeof(int));   //长度改为M-1
    format(A,N-1,K);                      //拿一元钱的孩子数减去1
    pailie(A,0,M-1,&sum);                 //长度改为M-1
    printf("%d\n",sum*N);               //排在第一个拿一元钱的孩子有N种情况，故结果有sum*(N)种
 }
return 0;
}

/*===================================================*/
void format(int *A,int N,int K)                  //此函数不变
{

  for(int i=0;i<(N+K);i++)
  {
    if(i<N)
    A[i]=1;
    else
    A[i]=2;
  }

  return;
}
/*===================================================*/
void pailie(int *A,int index,int length,int *sum)     //这个也不变
{

   int i=0,j=0;

   if(index==length)
    {
     panduan(A,length,sum);
    }
    else
     for(j = index;j < length; j++)
        {
            swap(&A[j],&A[index]);
            pailie(A,index+1,length,sum);
            swap(&A[j],&A[index]);
        }
return ;
}

/*===================================================*/
void swap(int *x,int *y)  //不变
{
  int z=(*x);
  (*x)=(*y);
  (*y)=z;
return ;
}
/*===================================================*/
void panduan(int *A,int M,int *sum)
{
  int num_of_yiyuan=1;               //售票员初始钱改为1

  for(int i=0;i<M;i++)
   {
     if(A[i]==1)
      num_of_yiyuan++;
      else
      num_of_yiyuan--;

      if(num_of_yiyuan<0)
       break;
   }
  if(num_of_yiyuan>=0)
   (*sum)++;
return ;
}

别忘点赞哦-.-