数据备份Backup HYSBZ - 1150
你在一家 IT 公司为大型写字楼或办公楼（offices）的计算机数据做备份。然而数据备份的工作是枯燥乏味
的，因此你想设计一个系统让不同的办公楼彼此之间互相备份，而你则坐在家中尽享计算机游戏的乐趣。已知办公
楼都位于同一条街上。你决定给这些办公楼配对（两个一组）。每一对办公楼可以通过在这两个建筑物之间铺设网
络电缆使得它们可以互相备份。然而，网络电缆的费用很高。当地电信公司仅能为你提供 K 条网络电缆，这意味
着你仅能为 K 对办公楼（或总计2K个办公楼）安排备份。任一个办公楼都属于唯一的配对组（换句话说，这 2K
个办公楼一定是相异的）。此外，电信公司需按网络电缆的长度（公里数）收费。因而，你需要选择这 K 对办公
楼使得电缆的总长度尽可能短。换句话说，你需要选择这 K 对办公楼，使得每一对办公楼之间的距离之和（总距
离）尽可能小。下面给出一个示例，假定你有 5 个客户，其办公楼都在一条街上，如下图所示。这 5 个办公楼分
别位于距离大街起点 1km, 3km, 4km, 6km 和 12km 处。电信公司仅为你提供 K=2 条电缆。
上例中最好的配对方案是将第 1 个和第 2 个办公楼相连，第 3 个和第 4 个办公楼相连。这样可按要求使用
K=2 条电缆。第 1 条电缆的长度是 3km-1km=2km ，第 2 条电缆的长度是 6km-4km=2km。这种配对方案需要总长
4km 的网络电缆，满足距离之和最小的要求。
分析：
最优解中，每两个配对的办公楼一定是相邻的。每两个办公楼之间的距离，记为：D1,D2,D3,D4,,,,D n-1。于是问题转化为：从数列D中选出不超过K个数（对应办公楼的K个配对），使他们的和最小，并且相邻的两个数不能同时被选（任一办公楼都属于唯一的配对组）。
然后策略是这样的：
K=1 显然最小边。
K>=2
选择最小值 Di，以及除了它旁边两个数之外，其他数的最小值。
或者 选最小值旁边的两个数。
所以可以得到推论：最优解中，最小值左右两侧的数要么同时选，要么都不选。因此我们可以先选择最小值，然后把Di-1 、Di 、Di+1 从数列中删除，把Di-1 + D i+1 - Di 插入到刚才删除Di的位置上。如果后来选了这个加上的数，相当于没有选Di，而是选的它旁边的两个数。
所以用链表和最小堆可以实现这个思想：
const int maxn = 1e6+11;int f[maxn],a[maxn],pre[maxn],nxt[maxn],v[maxn];
int n,m,p;
int x,ans;void up(int p)
{while(p > 1){if(a[f[p]] < a[f[p>>1]])//小顶堆{swap(f[p],f[p>>1]);swap(v[f[p]],v[f[p>>1]]);p>>=1;}else break;}
}void down(int l,int r)
{int t = 2*l;while(t<=r){if(t < r && a[f[t]] > a[f[t+1]])t++;if(a[f[l]] > a[f[t]]){swap(f[l],f[t]);swap(v[f[l]],v[f[t]]);l = t, t = 2*l;}else break;}
}void ins(int x)
{f[++p] = x; v[x] = p;//f数组：二叉堆，v数组：对应在二叉堆的位置up(p);
}void erase(int x)
{f[v[x]] = f[p];v[f[p]] = v[x];p--;up(v[x]),down(v[x],p);
}int main()
{cin >> n >>m;rep(i,1,n+1)scanf("%d",a+i);rep(i,1,n){a[i] = a[i+1] - a[i];//d[i]nxt[i] = i+1,pre[i+1] = i;//链表ins(i); }rep(i,1,m+1){x = f[1]; ans += a[x];if(pre[x] == 0 && nxt[x] == n)break;if(pre[x] == 0){erase(x),erase(nxt[x]);pre[nxt[nxt[x]]] = 0;}else if(nxt[x] == n){erase(x),erase(pre[x]);nxt[pre[pre[x]]] = n;}else{erase(x),erase(pre[x]),erase(nxt[x]);a[x] = a[pre[x]] + a[nxt[x]] - a[x];ins(x);pre[x] = pre[pre[x]],nxt[pre[x]] = x;//插入X，删除原来的三个数。nxt[x] = nxt[nxt[x]],pre[nxt[x]] = x;}}cout << ans << endl;return 0;
}