AcWing 147.数据备份

这题没有模板，全是思维。
拿到这个题目的第一步就是分析与转换：通过简单的看图分析可以得出：我们只会选择两个相邻的办公楼相连。那么这个问题就转化为了：从一个序列（原数组的差分数组）中挑出k个互不相邻的数，使他们的和最小（第一步还真让我全部想到了）。
但是真正的难点在于如何解决转化后的问题。我们可以从贪心思想上进一步考虑：如果k=2，那么是否一定要选到最小值呢？假设最小值为D[i]（D为差分数组），那么假如不选D[i-1]与D[i+1]，那么我们就要选择D[i]与D[j]（min（D[k]），且k≠i-1，i+1），必然选择最小值与除了D[i-1]与D[i+1]之外的次小值。那么假如选择D[i-1]与D[i+1]中的其中一个，那么D[i]就不能被选，显然这种情况不如上面那一种情况优。所以我们得出结论：D[i-1]与D[i+1]要么同时都不被选，要么同时被选。所以当k=2时，答案为min(D[i]+D[j],D[i-1]+D[i+1])。接下来的思路更加nb：由k=2推广到k>2，这是从特殊到一般。在计算机算法里，一般考虑继续采用k=2的算法，但是要将问题的规模缩小，变成原问题的子问题，到最后k=2时直接解决。这是一种常用的思路（递归、递推、分治、动规都用到了这一种缩小问题规模的思路）。那么我们就有了基本的思路：每次都在数组中做k=2时的算法，且要做到每一次都减少2个数（因为已经求出了两个数的和）。那么算法设计如下：初始化：建立一个链表，将差分数组中所有的数按顺序串起来。（设点p的左边节点为l[p]，右边节点为r[p]）每次对于最小值D[p]，我们将其取出后，把它的值更新为D[l[p]]+D[r[p]]-D[p]，并将答案加上D[p]，删去l[p]与r[p]两个节点（这个方法真是妙不可言，真的需要经验的积累与灵感的爆发）。那么假如我们第二次还选p节点，答案就会被更新成D[l[p]]+D[r[p]]，不会遗漏最优解。且删去l[p]与r[p]后不会再选到相邻的节点。
代码如下：

#include
#include
#include
#include
using namespace std;
const int N=2e5+5;
typedef long long ll;
ll a[N],d[N];
int l[N],r[N],idx;
bool st[N];
typedef pair PII;
priority_queue,greater> heap;
void remove(int p){
    st[p]=true;
    l[r[p]]=l[p];
    r[l[p]]=r[p];
}
int main(){
    int n,k;
    idx=n-1;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    d[0]=d[n]=1e9;
    for(int i=0;i<=n;i++){
        l[i]=i-1;
        r[i]=i+1;
        if(i>=1 && i
            d[i]=a[i+1]-a[i];
            heap.push({d[i],i});
        }
    }
    ll ans=0;
    while(k--){
        while(st[heap.top().second]) heap.pop();
        PII t=heap.top();
        int p=t.second;
        heap.pop();
        ans+=t.first;
        d[p]=d[l[p]]+d[r[p]]-d[p];
        remove(l[p]);remove(r[p]);
        heap.push({d[p],p});
    }
    cout<