微软应聘试题算法求解

Question

某日一友到微软应聘笔试，遇到这样一题，拿与各位分享：   有4个人过桥，这4个人单独过桥的时间分别为1分钟、2分钟、5分钟、10分钟；他们只有一个手电筒，一次过桥只能同时过两个人，速度按慢的人算，然后其中一个人再拿手电筒回来接其他的人再过去；请问他们按怎样的顺序过桥所花的时间最少？ 最少时间是多少？ 

Answer 1

10,5==> 5 <==   10+5
5,2 ==> 2 <==   5+2
2,1==>          2= 24

Answer 2

10,1   ==>  1 <==   10+1
5,1    ==>  1 <==   5+1
2,1    ==>          2= 19

Answer 3

2,1  ==>    1 <==   2+1
10,5 ==>    2 <==   10+2
2,1 ==>             2
=17

Answer 4

好像看过这样的题:
1,2 ==>
   <== 1
5,10 ==>
   <== 2
1,2 ==>17分钟

Answer 5

花了我2小时 :(#include <iostream.h>
#include <vector>
using namespace std;#define max(a,b)  (a>b?a:b)typedef struct treeNode{
    unsigned int time;
    vector<int> start,end;
    treeNode *firstChild,*nextSibling;
    bool result;
}TreeNode,*pTreeNode;void moveStart2End(vector<int> start, vector<int> end, int num1,int num2, vector<int> &nextStart, vector<int> &nextEnd)
{
    nextStart.assign(start.begin(),start.end());
    nextEnd.assign(end.begin(),end.end());
    nextEnd.push_back(nextStart[num1]);
    nextEnd.push_back(nextStart[num2]);
    nextStart.erase(nextStart.begin()+num1);
    nextStart.erase(nextStart.begin()+num2-1);
}void moveEnd2Start(vector<int> start, vector<int> end, int num, vector<int> &nextStart, vector<int> &nextEnd)
{
    nextStart.assign(start.begin(),start.end());
    nextEnd.assign(end.begin(),end.end());
    nextStart.push_back(nextEnd[num]);
    nextEnd.erase(nextEnd.begin()+num);
}void go(pTreeNode &first)
{
    pTreeNode preSibling = NULL;
    pTreeNode nextFirst;
    while(first != NULL){
for(int i=0; i<(first->start).size()-1; i++)
    for(int j=i+1; j<(first->start).size(); j++){
pTreeNode child = new TreeNode;
moveStart2End(first->start,first->end,i,j,child->start,child->end);
child->time = max((first->start)[i],(first->start)[j]) + first->time;
child->firstChild = NULL;
child->nextSibling = NULL;
if( (child->start).size() == 0)
    child->result = true;
else
    child->result = false;
if(preSibling == NULL) {
    first->firstChild = child;
    nextFirst = child;
    preSibling = child;
}
else{
    preSibling->nextSibling = child;
    preSibling = child;
} 
    }
first = first->nextSibling;
    }
    first = nextFirst;
}void back(pTreeNode &first)
{
    pTreeNode preSibling = NULL; 
    pTreeNode nextFirst;
    while(first != NULL){
for(int i=0; i<(first->end).size(); i++){
    pTreeNode child = new TreeNode;
    moveEnd2Start(first->start,first->end,i,child->start,child->end);
    child->time = (first->end)[i] + first->time;
    child->firstChild = NULL;
    child->nextSibling = NULL;
    child->result = false;
    if(preSibling == NULL) {
        first->firstChild = child;
nextFirst = child;
        preSibling = child;
    }
    else{
        preSibling->nextSibling = child;
preSibling = child;
    }
} 
first = first->nextSibling;
    }
    first = nextFirst;
}void midTrasverseTree(pTreeNode root,vector<int> &result)
{
    pTreeNode oldRoot = root;
    while(root){
if(root->result)
    result.push_back(root->time);
root = root->nextSibling;
    }
    if(oldRoot->firstChild !=NULL )
midTrasverseTree(oldRoot->firstChild,result);    
}int get_smallest(vector<int> result)
{
    int ret = result[0];
    for(int i=1;i<result.size();i++){
if(ret > result[i])
    ret = result[i];
    }     
    return ret;   
}void main()
{
    vector<int> result;
    int smallest;
    pTreeNode root = new TreeNode;
    root->time = 0;
    (root->start).push_back(1);
    (root->start).push_back(2);
    (root->start).push_back(5);
    (root->start).push_back(10);
    root->firstChild = NULL;
    root->nextSibling = NULL;
    root->result = false;
    pTreeNode oldRoot = root;
    for(int i=0;i<(root->start).size();i++){
go(root);
back(root);
    }
    go(root);
    midTrasverseTree(oldRoot,result);
    smallest = get_smallest(result);
    cout << "answer is:" << smallest << endl;
}

Answer 6

这个是ACM/ICPC里的一道练习题.

Answer 7

TO Paris_Luo(不懂):
弓虽！！！