例如,有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.
