（过河问题）在一个月黑风高的夜晚，有一群人在河的右岸，想通地_

（过河问题）在一个月黑风高的夜晚，有一群人在河的右岸，想通地唯一的一根独木桥走到河的左岸。在这伸手不见五指的黑夜里，过桥时必须借助灯光来照明。不幸的是，他们只有一盏灯。另外，独木桥上最多承受两个人同时经过，否则就会坍塌。每个人单独过桥都需要一定的时间，不同的人需要的时间可能不同。两个人一起过桥时，由于只有一盏灯，所有需要的时间是较慢的那个人单独过桥时所花的时间。现输入n（2<=n<100）和这n个人单独过桥时需要的时间，请计算总共最少需要多少时间，他们才能全部到达河的左岸。

例如，有3个人甲、乙、丙，他们单独过桥的时间分别为1、2、4，则总共最少需要的时间为7。具体方法是：甲、乙一起过桥到河的左岸，甲单独回到河的右岸并将灯带回，然后甲、丙再一起过桥到河的左岸，总时间为2+1+4 = 7。

const
  SIZE = 100;
  INFINITY = 10000;
  LEFT = true;
  RIGHT = false;
  LEFT_TO_RIGHT = true;
  RIGHT_TO_LEFT = false;
var
  n, i : integer;
  time : array[1..SIZE] of integer;
  pos : array[1..SIZE] of boolean;
function max(a, b : integer) : integer;
begin
  if a > b then
    max := a
  else
    max := b;
end;
function go(stage : boolean) : integer;
var
  i, j, num, tmp, ans : integer;
begin
  if (stage = RIGHT_TO_LEFT) then
  begin
    num := 0;
    ans := 0;
    for i := 1 to n do
      if pos[i] = RIGHT then
      begin
        inc(num);
        if time[i] > ans then ans := time[i];
      end;
    if   1              then
    begin
      go := ans;
      exit;
    end;
    ans := INFINITY;
    for i := 1 to n - 1 do
      if pos[i] = RIGHT then
        for j := i + 1 to n then
        if pos[j] = RIGHT then
        begin
        pos[i] := LEFT;
        pos[j] := LEFT;
        tmp := max(time[i], time[j]) + 2;
        if tmp < ans then  ans := tmp;
        pos[i] := RIGHT;
        pos[j] := RIGHT;
        end;
    go := ans;
  end
  else if (stage = LEFT_TO_RIGHT) then
  begin
    ans := INFINITY;
    for i := 1 to n do
      if  3           then
      begin
        pos[i] := RIGHT;
        tmp := 4;
        if tmp < ans then  ans := tmp;
        5;
      end;
    go := ans;
  end
  else
  go := 0;
  end;
begin
  readln(n);
  for i := 1 to n do
  begin
  read(time[i]);
  pos[i] := RIGHT;
  end;
  writeln(go(RIGHT_TO_LEFT));
end.

（过河问题）在一个月黑风高的夜晚，有一群人在河的右岸，想通地

问题信息

热门推荐

相关试题