Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 10218 | Accepted: 3859 |
Description
Input
Output
Sample Input
1 4 1 2 5 10
Sample Output
17
贪心算法:
1. 若n=1、2,一次过完。
2. n=3,由过桥最短的挨个把其他人送过河。
4、n>=4,
设用时分别为a,b,c,d,e,f...y,z(从小到大排序)
有两种策略,一种是由用时最短的人把用时最多的两个人挨个送过河,时间为2*a+y+z;
第二种: a,b先过河,a 回,然后y,z过河,b回,时间为:b+a+z+b=a+2*b+z;
比较两种方法的用时,最终得到最优答案。
#include"stdio.h" #include"stdlib.h" #define N 1005 int cmp(const void*a,const void*b) { return *(int*)a-*(int *)b; } int main() { int T,n,i,a[N],time; scanf("%d",&T); while(T--) { scanf("%d",&n); for(i=0;i<n;i++) { scanf("%d",&a[i]); } qsort(a,n,sizeof(a[0]),cmp); time=0; while(1) { if(n==1) { time+=a[0]; break; } else if(n==2) { time+=a[1]; break; } else if(n==3) { time+=(a[0]+a[1]+a[2]); break; } if(a[1]*2>a[0]+a[n-2]) { time+=(a[n-1]+a[n-2]+2*a[0]); n-=2; } else { time+=(2*a[1]+a[n-1]+a[0]); n-=2; } } printf("%d\n",time); } return 0; }
poj 1700 Crossing River,布布扣,bubuko.com
原文:http://blog.csdn.net/u011721440/article/details/25375205