ACM 贪心 Crossing River

滴，集训第十四天打卡。

台风终于来啦~

凉快了很多啊，但是湿漉漉的也很麻烦...

噫，好气。

POJ 1700 Crossing River

题目大意：有N个人要渡河，但是只有一艘船，船上每次最多只能载两个人，渡河的速度由两个人中较慢的那个决定，（例如1和2一起过河，时间算2）小船来回载人直到所有人都渡河，求最短的渡河时间。

思路：这里详细讲一下样例，先sort一下，然后可以有两种情况过河。第一种是先12去，然后1回，然后5 10去，然后2回，然后12去。第二种是1 10去，然后1回，然后15去，然后1回，然后12去。所以当N为123的时候可以单独考虑，然后其他用上述的贪心即可。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int main()
{
    int a[1005],i,t,n,sum;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        sum=0;
        for(i=0;i<n;i++)
        scanf("%d",&a[i]);
		if(n==3)
        sum=a[0]+a[1]+a[2];
        else if(n==2)
        sum=a[1];
        else if(n==1)
        sum=a[0];
        else
        {
        	 while(n>3)
	        {
	            sum=min(sum+2*a[1]+a[0]+a[n-1],sum+a[n-1]+a[n-2]+2*a[0]);
	            n-=2;
	        }
        }       
        printf("%d\n",sum);
    }
}