A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

..........有没有大能来发代码······
回复 使用道具 举报
考这个就完蛋了。。。。。我的天
回复 使用道具 举报
这是Java  面试 出的题吗
回复 使用道具 举报
SF_NEVERMORE 发表于 2015-10-8 22:38
甲乙过桥2分钟  甲回1分钟 丙丁过桥10分钟  乙回2分钟 甲乙过桥2分钟

我觉得二楼解的不错
回复 使用道具 举报
代码写得有点长,你自己优化一下,希望可以帮到你
  1. import java.util.ArrayList;

  2. /**
  3. * 思路:在桥这边枚举两个人过去,然后在桥那表让花时最小的送手电筒回来,
  4. * 然后继续枚举两个人过桥,再让花时最小的送手电筒回来,循环的,直到这边的人只剩下两个。
  5. */

  6. class Tie_2
  7. {
  8.         // 记录过程
  9.         private static String changes = "";
  10.          // 标记是否成功过桥,若成功过了,那么就跳出,不找了
  11.         private static boolean isCross = false;

  12.         public static void main(String[] args)
  13.         {
  14.                 ArrayList<Integer> here = new ArrayList<Integer>();
  15.                 ArrayList<Integer> there = new ArrayList<Integer>();
  16.                 init(here,there);

  17.                 // 枚举两个人过桥
  18.                 o:for(int i=0; i<here.size(); i++)
  19.                 {
  20.                         for(int j=0; j<here.size(); j++)
  21.                         {
  22.                                 if(i==j)
  23.                                         continue;
  24.                                 int timeone = here.get(i);
  25.                                 int timetwo = here.get(j);
  26.                                 if(!isCross){
  27.                                         crossBridge(here,there,timeone,timetwo,0);
  28.                                         init(here,there);
  29.                                 }else{
  30.                                         break o;
  31.                                 }
  32.                         }
  33.                 }
  34.         }

  35.         // 初始化数据
  36.         public static void init(ArrayList<Integer> here,ArrayList<Integer> there)
  37.         {
  38.                 here.clear();
  39.                 there.clear();
  40.                 here.add(1);
  41.                 here.add(2);
  42.                 here.add(5);
  43.                 here.add(10);
  44.         }

  45.         // 过桥
  46.         public static void crossBridge(ArrayList<Integer> a, ArrayList<Integer> b, int timeone, int timetwo,int allTime)
  47.         {
  48.                 // 取出花时最大的
  49.                 int bigTime = timeone > timetwo ? timeone : timetwo;
  50.                 changes += "这边:" + a +"  -------桥--------  " + "那边:"+b + "\n\t" +timeone + "和" + timetwo + "一起过桥!---用时:"+bigTime+"分\n";
  51.                 // 将过桥的两个存在b集合,代表过桥了
  52.                 b.add(timeone);
  53.                 b.add(timetwo);
  54.                 allTime += bigTime; // 一共用了多少时间

  55.                 // 把过桥的两个人在a集合中删除
  56.                 for(int i=0;i<a.size();i++)
  57.                         if(timeone==a.get(i)){
  58.                                 a.remove(i);
  59.                                 break;
  60.                 }
  61.                 for(int i=0;i<a.size();i++)
  62.                         if(timetwo==a.get(i)){
  63.                                 a.remove(i);
  64.                                 break;
  65.                 }
  66.                
  67.                 // 在这边找一个花时最小的送手电筒回去
  68.                 int smallTimeIndex = getSmallTime(b); // 花时最小的时间的角标
  69.                 changes += "这边:" + a +"  -------桥--------  " + "那边:"+b+"\n\t"
  70.                                 + b.get(smallTimeIndex)  + "送手电筒回去!---用时:" +b.get(smallTimeIndex)+"分\n";
  71.                 allTime += b.get(smallTimeIndex); // 累加时间
  72.                 a.add(b.get(smallTimeIndex)); // 送手电筒回去了,就添加到a集合
  73.                 b.remove(smallTimeIndex);

  74.                 // 出口判断
  75.                 if(a.size()==2 && b.size()==2)
  76.                 {
  77.                         bigTime = Math.max(a.get(0),a.get(1));
  78.                         allTime+=bigTime;
  79.                         if(allTime > 17)
  80.                         {
  81.                                 changes = "";
  82.                                 return;
  83.                         }
  84.                         System.out.println(changes +"\t"+ a.get(0)+"和"+a.get(1) +"一起过桥!---用时:"+bigTime+"分");
  85.                         System.out.println("\t一共花时:"+allTime+"分");
  86.                         isCross = true; // 标记已经成功过桥了
  87.                         changes = "";
  88.                         return;
  89.                 }

  90.                 // 继续枚举两个人过桥
  91.                 for(int i=0; i<a.size(); i++)
  92.                 {
  93.                         for(int j=0; j<a.size(); j++)
  94.                         {
  95.                                 if(i==j)
  96.                                         continue;
  97.                                 timeone = a.get(i);
  98.                                 timetwo = a.get(j);
  99.                                 if((allTime + (timeone > timetwo ? timeone : timetwo)) > 17)
  100.                                         continue;
  101.                                 crossBridge(a,b,timeone,timetwo,allTime);
  102.                         }
  103.                 }
  104.                
  105.         }

  106.         // 获取b集合中花时最小时间的角标
  107.         public static int getSmallTime(ArrayList<Integer> b)
  108.         {
  109.                 int small = Integer.MAX_VALUE;
  110.                 int index = -1;
  111.                 for(int i=0;i<b.size();i++)
  112.                         if(small > b.get(i))
  113.                         {
  114.                                 small = b.get(i);
  115.                                 index = i;
  116.                         }
  117.                 return index;
  118.         }
  119. }
复制代码

输出结果:
这边:[1, 2, 5, 10]  -------桥--------  那边:[]
        1和2一起过桥!---用时:2分
这边:[5, 10]  -------桥--------  那边:[1, 2]
        1送手电筒回去!---用时:1分
这边:[5, 10, 1]  -------桥--------  那边:[2]
        5和10一起过桥!---用时:10分
这边:[1]  -------桥--------  那边:[2, 5, 10]
        2送手电筒回去!---用时:2分
        1和2一起过桥!---用时:2分
        一共花时:17分
回复 使用道具 举报
我没算这个题,但是我好多年前就听过这个……
回复 使用道具 举报
ln0491 中级黑马 2015-10-21 09:49:56
27#
挺有意思的,。。。。。。。。
回复 使用道具 举报
12
您需要登录后才可以回帖 登录 | 加入黑马