本文主要是介绍杂题_POJ上的过桥问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
本文出自：http://blog.csdn.net/svitter
过桥问题解释：一条船可以坐两个人，但是有很多人要过河，所以送过一个人去，另一个人还要回来接。使所有人过河之后时间最短，如何求？
此问题曾作为阿里巴巴题目
初看此题想的太过简单，直接让跑的最快的送过去，自己再跑回来即可。其实不然。
函数g(a,b)表示过河，b(a)表示回来。如果过河时间分别为1，2，5，10
那么两种过河方案：
1.初想方案：
g（1，2）=2
g (1, 10) = 10
g (1, 5 ) = 5
b(1) * 2 = 2
sum =19
2.另一种方案：. g(1,2) =2
b(1) =1
g(5,10)=10
b(2)=2
g(1,2)=2
sum = 17
另一种方案就是让两个跑的快的先跑过去，然后一个带回来船，然后两个慢的跑过去，另一个跑的快的带回来船。
如此两种方案的速度分别为：
设跑的快的分别为a, b,跑的慢的为c, d
那么c, d过河需要的时间分别为：
1.a + a + c + d
2.a +ｂ＋ｂ＋ｄ
如此一来，求得ｂ＋ｂ与ａ＋ｃ的大小关系，则知道取哪种方案最佳。
题目有poj2573, poj1700
1700解题代码：（也有dfs，dp写法，但是我没理解）
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>using namespace std;int main()
{int n, sec;int time[1010];int t;int temp;int i, j, k;//freopen("test", "r", stdin);scanf("%d", &t);while(t--){scanf("%d", &n);memset(time, 0, sizeof(time));for(i = 0; i < n; i++)scanf("%d", &time[i]);if(n == 1)printf("%d\n", time[0]);else if(2 == n)printf("%d\n", time[0] > time[1] ? time[0] : time[1]);else if(3 == n)printf("%d\n", time[0] + time[1] + time[2]);else{sec = 0;sort(time ,time + n);temp = time[1]*2;while(n >=4){sec += time[0];sec += time[n-1];i = time[1] * 2;j = time[0] + time[n-2];if(i > j)sec += j;else sec += i;n -= 2;}if(2 == n)printf("%d\n", sec + time[1]);else if(3 == n)printf("%d\n", sec + time[0] + time[1] + time[2]);}}return 0;
}
2573：
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>using namespace std;struct outPut
{int front, end;outPut(int a, int b):front(a), end(b){}outPut(int a):front(a), end(-1){}
};void output(outPut *a)
{if(a->end != -1)printf("%d %d\n", a->front, a->end);elseprintf("%d\n", a->front);
}int main()
{int temp;int pe[1010];int i, j;int n;// cost timeint sec;//freopen("test", "r", stdin);queue <outPut> Queue;while(~scanf("%d", &n)){//printf("\nCase: \n");for(i = 0; i < n; i++)scanf("%d", &pe[i]);if(1 == n){printf("%d\n", pe[0]);printf("%d\n", pe[0]);}//..else if(2 == n){if(pe[0] > pe[1]){i = pe[0];j = pe[1];}else{i = pe[1];j = pe[0];}printf("%d\n", i);printf("%d %d\n", j, i);}else if(3 == n){sort(pe, pe+3);printf("%d\n", pe[0]+pe[1]+pe[2]);printf("%d %d\n", pe[0], pe[2]);printf("%d\n", pe[0]);printf("%d %d\n", pe[0], pe[1]);}else{sort(pe, pe+n);temp = pe[1] * 2;sec = 0;while(n >= 4){sec += pe[n-1];sec += pe[0];if(temp < pe[0] + pe[n-2]){Queue.push(outPut(pe[0], pe[1]));Queue.push(outPut(pe[0]));Queue.push(outPut(pe[n-2], pe[n-1]));Queue.push(outPut(pe[1]));sec += temp;} else{Queue.push(outPut(pe[0], pe[n-1]));Queue.push(outPut(pe[0]));Queue.push(outPut(pe[0], pe[n-2]));Queue.push(outPut(pe[0]));sec += pe[0] + pe[n-2];}n -= 2;}if(2 == n){outPut *tmp;printf("%d\n", sec + pe[1]);while(!Queue.empty()){tmp = &Queue.front();output(tmp);Queue.pop();}printf("%d %d\n", pe[0], pe[1]);}else if(3 == n){outPut *tmp;printf("%d\n", sec + pe[0] + pe[1] + pe[2]);while(!Queue.empty()){tmp = &Queue.front();output(tmp);Queue.pop();}printf("%d %d\n", pe[0], pe[2]);printf("%d\n", pe[0]);printf("%d %d\n", pe[0], pe[1]);}}}return 0;
}
这篇关于杂题_POJ上的过桥问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
