过桥问题的最短时间

问题：n个人要过桥，但是只有一个手电筒，并且同时只有两个人过去。每个人的过桥时间不同，取决于时间长的那个人。
            现在要求出最短的时间让所有人都过去？

例子：
4个人时间为 1  2   5   10
最短时间为17，方法为：1  2  过  1  回，5  10  过 2  回，1  2  过

我写的程序如下：

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


#define MIN    0
#define MAX    100

static int *time;
static int timenum;

static int *inpeople;
static int inpeoples;
static int *outpeople;
static int outpeoples;

int main(void)
{
    int i;
    int sumtime = 0;

    if(scanf("%d",&timenum) == EOF) {
        printf("Wrong\n");
        goto out;
    }
    if(timenum == 0) {
        printf("Wrong\n");
        goto out;
    }
    else if(timenum == 1) {
        if(scanf("%d",&sumtime) == EOF) {
            printf("Wrong\n");
        }
        goto out;
    }

    // timenum >= 2
    if(input() != 0) {
        printf("Wrong input\n");
        goto out;
    }

    sumtime = bridge();

out:
    printf("timenum is %d sumtime is %d\n",timenum,sumtime);
    return 0;
}

int input(void)
{
    int i = 0;

    time = malloc(timenum*sizeof(int));
    inpeople = malloc(timenum*sizeof(int));
    outpeople = malloc(timenum*sizeof(int));
    if(time == NULL || inpeople == NULL || outpeople == NULL) {
        printf("Wrong no mem\n");
        return -1;
    }

    while(i < timenum && scanf("%d",&time[i]) != EOF) {
        inpeople[i] = 1;
        outpeople[i] = 0;
        i++;
    }
    inpeoples = timenum;
    outpeoples = 0;
    if(i != timenum) {
        printf("Wrong i= %d\n",i);
        return -1;
    }

    return 0;
}

void min(int A[],int *x)
{
    int i;
    int ret = 0;
    *x = MAX;
    for(i=0;i<timenum;i++) {
        if(A[i] == 1 && time[i] < *x) {
            *x = time[i];
            ret = i;
        }
    }
    A[ret] = 0;
}

void max(int A[],int *x)
{
    int i;
    int ret = 0;
    *x = MIN;
    for(i=0;i<timenum;i++) {
        if(A[i] == 1 && time[i] > *x) {
            *x = time[i];
            ret = i;
        }
    }
    A[ret] = 0;
}

void insert(int A[],int x)
{
    int i;
    for(i=0;i<timenum;i++) {
        if(time[i] == x)
            break;
    }
    A[i] = 1;
}

int bridge(void)
{
    int sum = 0;
    int times = 0;
    int x,y;

    while(inpeoples > 0) {
        if(times % 2 == 0) {
            min(inpeople,&x);
            min(inpeople,&y);
        }
        else {
            max(inpeople,&y);
            max(inpeople,&x);
        }
        inpeoples -= 2;
        printf("%d and %d go times is %d\n",x,y,times);

        sum += y;

        insert(outpeople,x);
        insert(outpeople,y);
        outpeoples += 2;

        if(outpeoples == timenum)
            break;

        min(outpeople,&x);
        outpeoples--;
        printf("%d back times is %d\n",x,times);

        sum +=x;

        insert(inpeople,x);
        inpeoples++;

        times++;
    }
    return sum;
}

输入测试一：

4
1
6
8
12

打印结果一：

root@archer:/work/user-lib/bridge# ./main < input
1 and 6 go times is 0
1 back times is 0
8 and 12 go times is 1
6 back times is 1
1 and 6 go times is 2
timenum is 4 sumtime is 31

输入测试二：

12
1
6
8
12
15
20
33
42
65
78
83
90

打印结果二：

root@archer:/work/user-lib/bridge# ./main < input
1 and 6 go times is 0
1 back times is 0
83 and 90 go times is 1
6 back times is 1
1 and 6 go times is 2
1 back times is 2
65 and 78 go times is 3
6 back times is 3
1 and 6 go times is 4
1 back times is 4
33 and 42 go times is 5
6 back times is 5
1 and 6 go times is 6
1 back times is 6
15 and 20 go times is 7
6 back times is 7
1 and 6 go times is 8
1 back times is 8
8 and 12 go times is 9
6 back times is 9
1 and 6 go times is 10
timenum is 12 sumtime is 313