过河问题(POJ1700)

题目链接：http://poj.org/problem?id=1700

解题报告：

1、贪心算法，每次过两个速度最慢的人，抵消那个较慢的人的时间。

#include <stdio.h>

#include <algorithm>

using namespace std;

int a[];

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        int i;

        int time=;

        int n;

        scanf("%d",&n);

        for(i=;i<n;i++)

            scanf("%d",&a[i]);

        if(n==)

        {

            printf("%d\n",a[]);

            continue;

        }

        else

        {

            sort(a,a+n);

            ///当人数大于3时，让速度最慢的两个人过河。直至剩余2,或者3个人。

            for(i=n-;i>;i-=)

            {

                ///两种方案

                ///1、a[i]和a[i-1]两个人与a[0]一起过河，由a[0]送手电筒

                ///2、a[0]和a[1]首先过河，再a[0]过来，再a[i]和a[i-1]过来，再a[1]送手电筒

                time+=min(a[i]+a[i-]+*a[],a[]+a[]+a[i]+a[]);

            }

            if(i==)///两个人

                time+=a[];

            else time+=a[]+a[]+a[];///a[0]和a[2]过河，再a[0]送手电筒,再a[0]和a[1]过河。

        }

        printf("%d\n",time);

    }

    return ;

}