过河问题的代码实现

/*最佳方案构造：以下是构造N个人(N≥1)过桥最佳方案的方法：　　
1) 如果N=1、2，所有人直接过桥。　　
2) 如果N=3，由最快的人往返一次把其他两人送过河。　　
3) 如果N≥4，设A、B为走得最快和次快的旅行者，过桥所需时间分别为a、b；
 而Z、Y为走得最慢和次慢的旅行者，过桥所需时间分别为z、y。那么　　　　
 当2b＞a+y时，使用模式一将Z和Y移动过桥；　　　　
 当2b＜a+y时，使用模式二将Z和Y移动过桥；　　　　
 当2b＝a+y时，使用模式一将Z和Y移动过桥。
这样就使问题转变为N-2个旅行者的情形，从而递归解决之。
　    ……　　　　　　　　　
    A Z →　　　　　　　　　　
    A ←　　　　　　　　　　
    ……
也就是“由A护送到对岸，A返回”，称作“模式一”。

    ……　　　　　　　　　　
    ……　　
第n-2步：　　　A B →　　　
第n-1步：　　　　A ←　　　　
第n步：　　　  Y Z →　　
第n+1步：　　　　B ←　　　　　　　　　　
    ……
这个模式是“由A和B护送到对岸，A和B返回”，称作“模式二”。*/

#include <stdio.h>
#include <stdlib.h>

int cmp(const int *a, const int *b)
{
    return *a - *b;
}

int main()
{
    int *array = NULL;
    int total, n, tmp;
 int fast1, fast2, slow1, slow2;
    scanf("%d", &n);

 total = 0;
    if(array)
    {
        free(array);
    }
    array = (int *)malloc(sizeof(int) * n);
    tmp = n;
    while(tmp --)
    {
        scanf("%d", &array[tmp]);
    }

 /*库函数提供的快速排序算法，只需要实现比较函数就可以了*/
    qsort(array, n, sizeof(int), cmp);

 fast1 = array[0];       //最快的
 fast2 = array[1];       //次最快的
 slow1 = array[n - 2];   //次慢
 slow2 = array[n - 1];   //最慢的

 while (1)
 {
  /*如果只有一个或两个或者三个，以最慢的人为参考*/
  if(1 == n)
  {
   total += slow2;
   break;
  }
  if(2 == n)
  {
   total += array[1];
   break;
  }
  if (3 == n)
  {
   total += slow2 + slow1 + fast1;
   break;
  }

  /*根据情况分别用模式一和模式二护送最慢的两个过桥*/
  if(2 * fast2 >= fast1 + slow1)
  {
   /*用最快的护送最慢的两个所需要的时间*/
   total += (slow1 + slow2 + 2 * fast1);
  }
  else
  {
   /*用最快的两个护送最慢的两个所需要的时间*/
   total += 2 * fast2 + fast1 + slow2;
  }
  n -= 2;
  slow2 = array[n - 1];
  slow1 = array[n - 2];  
 }

    if(array)
    {
        free(array);
    }     
 printf("%d\n", total);

    return 0;
}