passbridge.c

线形的哦。很牛的

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

int n, *a;

int cmp_int(const void *pvData1, const void *pvData2)
{
    int i1 = *(int *)pvData1;
    int i2 = *(int *)pvData2;
    if (i1 == i2)
    {
        return 0;
    }
    else if (i1 < i2)
    {
        return -1;
    }
    else
    {
        return 1;
    }
}

void print1(int a, int b)
{
    printf("%d->\n", a);
    printf("<-%d,%d\n", a, b);
}

void print2(int a, int b, int c, int d)
{
    printf("%d->\n", a);
    printf("<-%d,%d\n", c, d);
    printf("%d->\n", b);
    printf("<-%d,%d\n", a, b);
}

int pass_bridge()
{
    int total;
    int i;
    if (n <= 0)
    {
        return 0;
    }
    if (n == 1)
    {
        printf("<-%d\n", a[0]);
        return a[0];
    }
    if ((n % 2) == 0)
    {
        printf("<-%d,%d\n", a[0], a[1]);
        total = a[1];
        i = 2;
    }
    else
    {
        printf("<-%d,%d\n", a[0], a[1]);
        print1(a[0], a[2]);
        total = a[0] + a[1] + a[2];
        i = 3;
    }
    for (; i < n; i+=2)
    {
        if (2*a[1] < a[0] + a[i])
        {
            total += 2*a[1] + a[0] + a[i + 1];
            print2(a[0], a[1], a[i], a[i + 1]);
        }
        else
        {
            total += a[0] + a[i] + a[0] + a[i + 1];
            print1(a[0], a[i]);
            print1(a[0], a[i + 1]);
        }
    }
    return total;
}

int main()
{
    int i;
    int total;
    printf("input n:\n");
    scanf("%d", &n);
    a = (int *)malloc(sizeof(int)*n);
    printf("input a[]:\n");
    for (i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }
    qsort(a, n, sizeof(int), cmp_int);
    printf("\nsteps:\n");
    total = pass_bridge();
    printf("\ntotal = %d\n", total);
    free(a);
    return 0;
}