UVA10037 过桥问题/微软面试题/五人过桥问题

69 阅读 0 评论 46 点赞

我是靠谱客的博主发嗲大门，最近开发中收集的这篇文章主要介绍UVA10037 过桥问题/微软面试题/五人过桥问题，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意:

夜晚有n个人想要过桥，桥很窄只允许两个人通过，并且由于天色很黑，必须拿着手电筒过桥，手电筒只有一个。问n个人通过这座桥最少需要多少时间？

输入:

共有T组数据，每组数据有n(<1000)表示人数，之后的n个数字表示每个人过桥的时间t(<=100)。

样例：
1
4
1 2 5 10

输出:

每组过桥的时间，及过桥的方法。如果以最短时间通过桥的方法不止一种，任意输出一种即可。

样例：
17
1 2
1
5 10
2
1 2

我们先将每个人过桥的时间进行排序，设第i个人过桥的时间为dp[i]。当前桥边只剩两人，分析可知过桥的方法有两种。¹
①最快的人返回，带最慢的人过桥。最快的人再次返回，带次慢的人返回。
dp[i] = 2time[1] + time[i] + time[i-1]
②最快的人返回，将等交给最慢和次慢的人。次快的人返回，和最快的人一同返回。
dp[i] = time[1] + min{time[i], time[i-1]} + time[2] + time[2] = time[1] + 2time[2] + time[n]

微软面试题也出现过类似问题：4个人在晚上过一座小桥，过桥时必须要用到手电筒，只有一枚手电筒，每次最多只可以有两人通过， 4个人的过桥速度分别为1分钟、2分钟、5分钟、10分钟，试问最少需要多长时间4人才可以全部通过小桥？同样可以用上述方法解决。

五人提灯过独木桥也与此类似：有一盏灯能使用30s，要在灯熄灭前通过这座桥。一家五口人每个人过桥速度不同：哥哥1s，弟弟3s，爸爸6s，妈妈8s，奶奶12s。每次只能过两个人。过去后对岸要有一个人把灯送回来。最短需要29s，大家可以先自己尝试一下。ヽ(￣▽￣)ﾉ

AC代码：

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <iostream>
using namespace std;

int main()
{
    int tcase = 0;
    scanf("%d",&tcase);
    while(tcase--)
    {
        int n;
        scanf("%d",&n);

        int a[1020];
        memset(a, 0, sizeof(a));
        for(int i = 1; i <= n; i++)
            scanf("%d",&a[i]);
        sort(a, a+n+1);

        int timeCou = 0, rest;
        for(rest = n; rest >= 4; rest -= 2){
            timeCou += min(2*a[1] + a[rest] + a[rest-1], a[1] + 2*a[2] + a[rest]);
        }
        if(rest == 3) timeCou += a[1] + a[2] + a[3];
        else if(rest == 2) timeCou += a[2];
        else timeCou += a[1];
        printf("%dn", timeCou);

        for(rest = n; rest >= 4; rest -= 2){
            int dp1 = 2*a[1] + a[rest] + a[rest-1];
            int dp2 = a[1] + 2*a[2] + a[rest];
            if(dp1 < dp2){
                printf("%d %dn",a[1], a[rest-1]);
                printf("%dn",a[1]);
                printf("%d %dn",a[1], a[rest]);
                printf("%dn",a[1]);
            }
            else{
                printf("%d %dn",a[1], a[2]);
                printf("%dn",a[1]);
                printf("%d %dn",a[rest-1], a[rest]);
                printf("%dn",a[2]);
            }
        }
        if(rest == 3){
            printf("%d %dn",a[1], a[2]);
            printf("%dn", a[1]);
            printf("%d %dn",a[1], a[3]);
        }
        else if(rest == 2) printf("%d %dn", a[1], a[2]);
        else printf("%dn", a[1]);
        if(tcase) printf("n");
    }
    return 0;
}