3. 【NOIP2010】烽火传递

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

补全程序：

#include<iostream>
using namespace std;
const int SIZE=100;
int n,m,r,value[SIZE],heap[SIZE],
    pos[SIZE],home[SIZE],opt[SIZE];
void swap(int i,int j) {
    int tmp;
    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;
}
void add(int 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) {
    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 (heap[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;
}

选择题：

1. ①处应填（ ）
   {{ select(1) }}

• k
• opt[k]
• opt[r]
• pos[k]

2. ②处应填（ ）
   {{ select(2) }}

• home[k]=r
• home[r]=opt[k]
• home[r]=k
• home[pos[r]]=opt[k]

3. ③处应填（ ）
   {{ select(3) }}

• r/=2
• j=i+i
• j+=j
• j=i+i-1

4. ④处应填（ ）
   {{ select(4) }}

• swap(heap[i],heap[i])
• heap[i]=heap[j]
• swap(i,j)
• swap(j,r)

5. ⑤处应填（ ）
   {{ select(5) }}

• heap[1]
• value[i]+heap[r]
• heap[r]
• value[i]+heap[1]

6. ⑥处应填（ ）
   {{ select(6) }}

• i-m
• i-m+1
• pos[i-m]
• pos[i-m+1]