不是VIP会员,不能显示答案

题目解答

题目:
(烽火传递)烽火台又称烽燧,是重要的军事防御设施,一般建在险要处或交通要道上。一旦有敌情发生,白天燃烧柴草,通过浓烟表达信息;夜晚燃烧干柴,以火光传递军情。在某两座城市之间有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] :=  opt[k]   ; 
    pos[k] := r; 
       home[r]:=k   ; 
    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 
             j:=2*i   ; 
        if heap[i] > heap[j] then 
        begin 
             swap(i,j)    ; 
            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] :=  value[i]+heap[1]   ; 
        remove(  i-m   ); 
        add(i); 
    end; 
    writeln(heap[1]); 
end. 
考点:
分析:
解答:
评论:
老师: