小学奥数体、两人过河

题目描述

有 n 个人希望在晚上通过一座桥。在任何时刻，最多只能有两个人在桥上，并且必须要带着手电筒才能过桥。现在只有一个手电筒，所以必须安排某种顺序，使得手电筒可以被带回去让更多的人过桥。每个人都有不同的过桥时间，两个人一起过桥所用的时间等于其中较慢的一个人的过桥时间。现求所有人过桥的最短时间。

---

输入

第一行一个整数 n。（1≤n≤1000）

接下来 n 行，每行一个整数表示第 i 人的过桥时间 TiTi。（1≤Ti≤100）

输出

输出所有人过桥的最短时间。

---

样例输入

4
1
5
2
10

样例输出

17

样例说明

让 1,2 先过桥，然后让 1 回来，让 5,10 过桥，然后 2 回来再和 1 一起过桥，时间为 2+1+10+2+2=17。

---

数据规模与约定

时间限制：1 s

内存限制：256 M

100% 的数据保证 1≤n≤1000

思路

• n == 1 直接过河
• n == 2 耗时为慢的人
• n == 3 耗时为最慢的人+次慢的人
• n >= 4 有两种方案：
• 方案一：最快的人和次快的人过去，最快的人回来，然后最慢的人跟次慢的人过去，次快的人回来；
• 方案二：最快的人跟最慢的人过去，最快的人回来，然后跟次慢的人过去，最快的人回来；

代码演示1

#include <stdio.h>

#define min(a, b) ((a) > (b) ? (b) : (a))

void quick_sort(int *arr, int l, int r) {
    if (l >= r) return ;
    int x =l, y = r, z = arr[l];
    while (x < y) {
        while (x < y && arr[y] >= z) --y;
        if (x < y) arr[x++] = arr[y];
        while (x < y && arr[x] <= z) ++x;
        if (x < y) arr[y--] = arr[x];
    }
    arr[x] = z;
    quick_sort(arr, l, x - 1);
    quick_sort(arr, x + 1, r);
    return ;
}
int n, num[1005], ans;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &num[i]);
    quick_sort(num, 1, n);
    for (int i = n; i; i -= 2) {
        if (i == 1 || i == 2) {
            ans += num[i];
        } else if (i == 3) {
            ans += num[2] + num[1] + num[3];
            break;
        } else {
            ans += min(num[i] + num[1] + num[i - 1] + num[1], num[2] + num[2] + num[1] + num[i]);
        }
        //num[i] + num[1] + num[i - 1] + num[1] :方案 二
        //num[2] + num[2] + num[1] + num[i] :方案1 
    }  
    printf("%d\n", ans);
    return 0;
}

代码演示2

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

#define min(a, b) ((a) > (b) ? (b) : (a))

int n, num[1005], ans;

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

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &num[i]);
    qsort(num + 1, n, sizeof(int), comp); //升序
    for (int i = n; i; i -= 2) {
        if (i == 1 || i == 2) {
            ans += num[i];
        } else if (i == 3) {
            ans += num[2] + num[1] + num[3];
            break;
        } else { //n >= 4
            ans += min(num[i] + num[1] + num[i - 1] + num[1], num[2] + num[2] + num[1] + num[i]);
        }
        //num[i] + num[1] + num[i - 1] + num[1] :方案 二
        //num[2] + num[2] + num[1] + num[i] :方案1 
    }  
    printf("%d\n", ans);
    return 0;
}