首页 > 试题广场 >

(峰火传递)烽火台又称烽燧,是重要的军事防御措施,一般建在险

[填空题]
(峰火传递)烽火台又称烽燧,是重要的军事防御措施,一般建在险要处或交通要道上。一旦有敌情发生,白天燃烧柴草,通过浓烟表达信息;夜晚燃烧干柴,以火光传递军情。在某两座城市之间有n个烽火台,每个烽火台发出信号都有一定的代价。为了使情报准确地传递,在连续m个烽火台中,至少要有一个发出信号。现输入n、m和每个烽火台发出信号的代价,请计算总共最少花费多少代价,才能使敌军来袭之时,情报能在这两座城市之间准确传递。
例如,有5个烽火台,它们发出信号的代价依次为1、2、5、6、2,且m为3,则总共最少花费的代价为4,即由第2个和第5个烽火台发出信号。

const
  SIZE = 100;
var
  n, m, r, i : integer;
  value, heap, pos, home, opt : array[1..SIZE] of integer;
    //heap[i]表示用顺序数组存储的堆heap中第i个元素的值
    //pos[i]表示opt[i]在堆heap中的位置,即heap[pos[i]]=opt[i]
    //home[i]表示heap[i]在序列opt中的位置,即opt[home[i]]=heap[i]
procedure swap(i, j : integer);
//交换堆中的第i个和第j个元素
var
  tmp : integer;
begin
  pos[home[i]] := j;
  pos[home[j]] := i;
  tmp := heap[i];
  heap[i] := heap[j];
  heap[j] := tmp;
  tmp := home[i];
  home[i] := home[j];
  home[j] := tmp;
end;
procedure add(k : integer); // 在堆中插入opt[k]
var
  i : integer;
begin
  inc(r);
  heap[r] := 1;
  pos[k] := r;
  2;
  i := r;
  while (i > 1) and (heap[i] < heap[i div 2]) do
  begin
    swap(i, i div 2);
    i := i div 2;
  end;
end;
procedure remove(k : integer); // 在堆中删除opt[k]
var
  i, j : integer;
begin
  i := pos[k];
  swap(i, r);
  dec(r);
  if i = r + 1 then  exit;
  while (i > 1) and (heap[i] < heap[i div 2]) do
  begin
    swap(i, i div 2);
    i := i div 2;
  end;
  while i + i <= r do
  begin
    if (i + i + 1 <= r) and (heap[i + i + 1] < heap[i + i]) then
      j := i + i + 1
    else
      3;
    if heap[i] > heap[j] then
    begin
      4;
      i := j;
    end
    else
      break;
  end;
end;
begin
  readln(n, m);
  for i := 1 to n do   read(value[i]);
  r := 0;
  for i := 1 to m do
  begin
    opt[i] := value[i];
    add(i);
  end;
  for i := m + 1 to n do
  begin
    opt[i] := 5;
    remove(6);
    add(i);
  end;
  writeln(heap[1]);
end.

这道题你会答吗?花几分钟告诉大家答案吧!