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

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

1#include<iostream>2#include<cstring>3using namespace std;4const int SIZE=100;5int n,m,r,value[SIZE],heap[SIZE],6    pos[SIZE],home[SIZE],opt[SIZE];7    //hep[i]表示用顺序数组储存的堆heap中第i个元素的值8    //pos[i]表示opt[i]在堆heap中的位置，即heap[pos[i]]=opt[i]9    //home[i]表示heap[i]在序列opt中的位置，即opt[home[i]]=heap[i]10 11void swap(int i,int j)//交换堆中的第i个和第j个元素12{13    int tmp;14    pos[home[i]]=j;15    pos[home[j]]=i;16    tmp=heap[i];17    head[i]=head[j];18    heap[j]=tmp;19    tmp=home[i];20    home[i]=home[j];21    home[j]=tmp;22}23void add(int k)//在堆中插入opt[k]24{25    int i;26    r++;27    heap[r]=        ①      ;28    pos[k]=r;29             ②        ;30    i=r;31    while( (i>1) && (heap[i]<heap[i/2]) )32    {33        swap(i,i/2);34        i/=2;35    }36}37void remove(int k)//在堆中删除opt[k]38{39    int i,j;40    i=pos[k];41    swap(i,r);;42    r--;43    if(i==r+1)44       return ;45    while( (i>1)&&(heap[i]<heap[i/2]) )46    {47        swap(i,i/2);48        i/=2;49    }50    while(i+i<=r)51    {52        if( (i+i+1<=r) && (heap[i+i+1]<heap[i+i]) )53            j=i+i+1;54        else55                    ③       ;56        if(heap[i]>heap[j])57        {58                    ④        ;59            i=j;60        }61        else62            break;63    }64}65 66int main()67{68    int i;69    cin>>n>>m;70    for(i=1;i<=n;i+++)71        cin>>value[i];72    r=0;73    for(i=1;i<=m;i++)74    {75        opt[i]=value[i];76        add(i);77    }78    for(i=m+1;i<=n;i++)79    {80        opt[i]=         ⑤       ;81        remove(        ⑥       );82        add(i);83    }84    cout<<heap[1]<<endl;85    return 0;86}