当前位置:首页 > Java技术 > 解决N个人过桥时间最短问题(Java版本)

解决N个人过桥时间最短问题(Java版本)

2022年11月09日 19:52:22Java技术6

 

【问题描述】

n个人要晚上过桥,在任何时候最多两个人一组过桥,每组要有一只手电筒。在这n个人中只有一个手电筒能用,因此要安排以某种往返的方式来返还手电筒,使更多的人可以过桥。

  注意:每个人的过桥速度不同,每组的速度由过桥最慢的人所用的时间决定,约定n<=1000,并且没有人的过桥时间会超过100秒。

         【输入】

  1.  输入的第一行给出n,
  2.  接下来的n行给出每个人的过桥时间,不会超过1000人,且没有人的过桥时间会超过100秒。 4 1 2 5 10   

         【输出】   

 输出的第一行给出所有n个人过桥的总的秒数,接下来的若干行给出实现策略。每行包括一个或两个整数,表示组成一组过桥的一个或两个人,以所用的时间标识。
 总共:17 秒    
 去:1  2    
 回:1   
 去:5  10  
 回:2   
 去:1   2

【分析】由于一次过桥最多两人且手电筒需要往返传递,因此以两个成员过桥为一个分析单位,计算过桥时间。以按过桥时间递增的顺序将n个成员排序。则a[1]是最快的人,a[2]次之,a[n]是最慢的人,a[n-1]是倒数第二慢的人。在相对状况下考虑,则有两种方案:

  1.  用最快的成员a[1]传递手电筒帮助最慢的a[n]和a[n-1]过桥,易知来回所用的时间为2*a[1]+a[n]+a[n-1]
  2. 用最快的成员a[1]和次快的成员a[2]传递手电筒帮助最慢的a[n]和a[n-1]过桥,具体方案如下:

              1.a[1]和a[2]到对岸,所用时间为a[2];

              2.a[1]返回,将手电筒给最慢的a[n]和a[n-1],并且a[n]和a[n-1]到对岸后将手电筒交给a[2],所用时间为:a[1]+a[n];

              3.a[2]返回,所用时间为a[2];

              综合起来方案二所用的总时间为2*a[2]+a[n]+a[1]。

显然,两种方案的好坏取决于他们的总时间,若2a[1]+a[n]+a[n-1]<2a[2]+a[n]+a[1],即采用第一种方案,否则采用第二种方案。我们每次帮助最慢的两个人过桥,累加时间,最后可能出现的两种情况:

            1.对岸剩下两个队员,全部过桥,时间为a[2];

            2.对岸剩下三个队员,用最快的成员传递手电筒,帮助最慢的成员过桥,然后与次慢的成员一起过桥,时间为:a[1]+a[n-1]+a[n],注意,这里的n=3。

参考博主:解决N个人过桥时间最短问题(Java版本)

package com.wxw.online;

import java.util.Scanner;

/**
 * @Author: wxw
 * @create: 2019-10-17-10:41
 */

public class GreedBridge {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n, i, k;//人数为n,i,j,k为循环控制变量,数组存储过桥时间
        int[] a = new int[1024];
        int sum = 0; //过桥总时间
        n = sc.nextInt();
        for (i = 1; i <= n; i++)
            a[i] = sc.nextInt();
        if (n == 1) {
            System.out.format(a[1] + "%n" + a[1]);
        }
        k = n;
        while (k > 3)    //求总时间
        {
            //分情况讨论
            if (a[1] + a[k - 1] < 2 * a[2])
                sum += a[k] + a[1] * 2 + a[k - 1];
            else
                sum += a[2] * 2 + a[1] + a[k];
            k -= 2;
        }
        if (k == 2)    //对岸剩下两个成员
            sum += a[2];
        else        //对岸剩下3个成员
            sum += a[1] + a[2] + a[3];
        System.out.println(sum);//输出n个人的过桥时间
        k = n;
        while (k > 3)    //输出具体方案
        {
            if (a[1] + a[k - 1] < 2 * a[2])    //输出用a[1]传递手电筒方案
            {
                System.out.format(a[1] + " " + a[k] + "%n" + a[1] + "%n" + a[1] + " " + a[k - 1] + "%n" + a[1]);
            } else                        //输出用a[1]、a[2]传递手电筒发的方案
            {
                System.out.format(a[1] + " " + a[2] + "%n" + a[1] + "%n" + a[k] + " " + a[k - 1] + "%n" + a[2] + "%n");
                k -= 2;
            }
            if (k == 2)
                System.out.println(a[1] + " " + a[2]);
            else {

                System.out.format(a[1] + " " + a[3] + "%n" + a[1] + "%n" + a[1] + " " + a[2]);
            }

        }
    }
}

 

作者:半糖君
来源链接:https://www.cnblogs.com/iswxw/p/11690939.html

版权声明:
1、JavaClub(https://www.javaclub.cn)以学习交流为目的,由作者投稿、网友推荐和小编整理收藏优秀的IT技术及相关内容,包括但不限于文字、图片、音频、视频、软件、程序等,其均来自互联网,本站不享有版权,版权归原作者所有。

2、本站提供的内容仅用于个人学习、研究或欣赏,以及其他非商业性或非盈利性用途,但同时应遵守著作权法及其他相关法律的规定,不得侵犯相关权利人及本网站的合法权利。
3、本网站内容原作者如不愿意在本网站刊登内容,请及时通知本站(javaclubcn@163.com),我们将第一时间核实后及时予以删除。


本文链接:https://www.javaclub.cn/java/69232.html

标签: Java版本
分享给朋友: