（烽火传递） 烽火台又称烽燧，是重要的军事防御设施，一

第1题

（烽火传递） 烽火台又称烽燧，是重要的军事防御设施，一般建在险要处或交通要道上。 一旦有敌情发生，白天燃烧柴草，通过浓烟表达信息；夜晚燃烧干柴，以火光传递军情。在 某两座城市之间有 n 个烽火台，每个烽火台发出信号都有一定的代价。为了使情报准确地传 递，在连续的 m个烽火台中至少要有一个发出信号。现输入 n、m和每个烽火台发出信号的代 价，请计算总共最少花费多少代价，才能使敌军来袭之时，情报能在这两座城市之间准确传 递。 

例如，有 5 个烽火台，他们发出信号的代价依次为 1，2，5，6，2，，且 m为 3，则总共最少 花费代价为 4，即由第 2 个和第 5 个烽火台发出信号。

#include<iostream>
#include<cstring>
using namespace std;
const int SIZE=100;
int n,m,r,value[SIZE],heap[SIZE],
 pos[SIZE],home[SIZE],opt[SIZE];
 //hep[i] 表示用顺序数组储存的堆 heap 中第 i 个元素的值
 //pos[i] 表示 opt[i] 在堆 heap中的位置，即 heap[pos[i]]=opt[i]
 //home[i] 表示 heap[i] 在序列 opt 中的位置，即 opt[home[i]]=heap[i]
void swap(int i,int j)// 交换堆中的第 i 个和第 j 个元素
{
 int tmp;
 pos[home[i]]=j;
 pos[home[j]]=i; 
 tmp=heap[i];
 head[i]=head[j];
 heap[j]=tmp;
 tmp=home[i];
 home[i]=home[j];
 home[j]=tmp; 
}
void add(int k)// 在堆中插入 opt[k]
{
 int i;
 r++;
 heap[r]= ① ;
 pos[k]=r;
② ;
 i=r;
 while( (i>1) && (heap[i]<heap[i/2]) )
 {
 swap(i,i/2);
 i/=2;
 }
}
void remove(int k)// 在堆中删除 opt[k]
{
 int i,j;
 i=pos[k];
 swap(i,r);;
 r--;
 if(i==r+1)
 return ;
 while( (i>1)&&(heap[i]<heap[i/2]) )
 {
 swap(i,i/2); 
 i/=2;
 }
 while(i+i<=r)
 {
 if( (i+i+1<=r) && (heap[i+i+1]<heap[i+i]) )
 j=i+i+1;
 else
③ ;
 if(hea[i]>heap[j])
 {
④ ;
 i=j;
 }
 else
 break;
 }
} 
int main()
{
 int i;
 cin>>n>>m;
 for(i=1;i<=n;i+++)
 cin>>value[i];
 r=0;
 for(i=1;i<=m;i++)
 {
 opt[i]=value[i];
 add(i);
 }
 for(i=m+1;i<=n;i++)
 { 
 opt[i]= ⑤ ;
 remove( ⑥ );
 add(i);
 } 
 cout<<heap[1]<<endl;
 return 0;
}