问题 G: 过桥问题

准确来说这题是一道贪心题目。
可能确实有些难度，但具体分析后就不难了。首先我们就先看看样例吧，其实可能会有人连样例都看不懂哈哈哈哈哈

题解有点长要细心看哦

（第一整体！！！）五个人分别需要1 3 6 8 12分钟才能过桥，先说29这个答案是怎么来的。我们先让1 3两个人过桥用了3min，然后1把手电筒拿回来，共计4min，再看8 12（因为只记最大时长，所以我们要把时长最大的两个人先运过去，这样8分钟的这个人就不用算上时间啦）过桥共计16min，这时候需要个人把手电筒拿回来，这就是我们刚刚为什么要把3运过去的原因了，因为他把手电筒拿回来所需的时间是最短的（因为1在第一次过桥的时候要把手电筒拿回来，所以这次只能是倒数第二小的3将其拿回来），这时候总计19min。
这时候再看还剩下谁 1 3 6，发现1 3为了运手电筒回来了，而最大的8和12过桥了，所以我们可以把这一次搬运视为一个整体。也就是让最小的两个过桥先把一个人运过去（运过去的用处是可以更快的把手电筒拿回来），然后让此时最大的两个人过桥，再让倒数第二小的人（即刚刚被运过去的人）把手电筒带回来。

（第二整体！！！）再看第二部分，这时候只有三个人1 3 6，很明显我们先把1 6送过去，总计25min，再让1回来，总计26min，最后让1 3过去，总计29min.我们得到了样例的答案，那么1 3 6三个人的搬运也可一视为一个整体，这时候不需要特意运一个人过去来搬运手电筒，我们可以让1来回跑（能者多劳），这样就可以把三个人都运过去了。
最后也就是这道题只有两种情况：1、让两个时间最小的人把两个时间最大的人搬运过去。2、让一个时间最短的人把两个时间最大的人搬运过去。
最后总结一下，如果只有两个人，那么过桥时间就是耗时较长的那个人的时间，如果只有三个人，那么就如样例里的第二个整体一样，如果有五或者更大的奇数就可以先按照样例中的第一个整体来，会发现每次减少的是两个人，最后就只剩下三个人，那么就是第二整体。在比如四或者更大的偶数，一开始也可以运用第一整体的方法一直减少人数，直到最后肯定只剩下两个人，那么两个人过桥时间也显而易见了。

上代码！！！

#include<stdio.h>

#include <algorithm>

using namespace std;

int main()
{
    int n, a[1005], i, j, sum;
    while (scanf("%d", &n) != EOF)
    {
        sum = 0;//不要忘记归零哦
        for (i = 0; i < n; i++)
        {
            scanf("%d", &a[i]);
        }
        sort(a, a + n);//排序，当然也可以用冒泡选择插入啦，只是sort比较方便而已
        while (n > 1)
        {
            if (n == 2)//最后只剩下两个人
            {
                sum += a[1];
                break;
            }
            else if (n == 3)//最后只剩下三个人（第二整体）
            {
                sum += a[0] + a[1] + a[2];
                break;
            }
            else
            {
                sum += a[1] + a[0] + a[n - 1] + a[1];//也就是第一整体的搬运
                n -= 2;
            }
        }
        printf("%d\n", sum);
    }
    return 0;
}
/*嘿嘿
在这里预祝zyy女士生日快乐🐖（鲜花*3）*/
//（如果路人看到这个就当没看到吧哈哈哈）

原文地址：http://www.cnblogs.com/myy-zzb/p/16881419.html