[算进] 数据备份

Problem

Luogu 题目地址

ACwing 题目地址

Sulotion

代码短，思维强，实现妙（就算猜出性质也不一定会实现），神仙题啊，科科（我太菜了而已）。

• 首先有一个显然的性质：选出来的这 \(k\) 对点一定相邻。

根据这个性质，我们做第一步问题转换：记两个点 \(i\) 和 \(i+1\) 之间的距离为 \(D_i\)，那么我们就得到一个长度为 \(n-1\) 的数组 \(D\)，我们要在 \(D\) 中选出 \(k\) 个数，并且这 \(k\) 个数两两不能相邻。

（做到这里就不会了是吧？）既然没有什么头绪，我们就从 \(k=1\) 的情况逐步推起，考虑像 [算进]序列 （就是上一题，虽然这两题看起来毫无联系的样子）一样用数学归纳法解决问题。

• \(k=1\)

显然我们要选 \(\min\{D_i\}\)，并且记这个数为 \(D_m\)。

• \(k=2\)

显然决策集合只有两个部分：1.选 \(D_m + D_{m'}\) （\(D_{m'}\) 是不与 \(D_m\) 相邻的最小值）；2.选 \(D_{m-1} + D_{m+1}\)。

如果你不理解的话，这里有解释：如果我们考虑选 \(D_{m-1}\) 或者 \(D_{m+1}\)，这就要使 \(D_m\) 换成别的数，假设将 \(D_m\) 换成 \(D_x\)，\(D_{m-1}+D_x\) （假设选 \(D_{m-1}\)，\(D_{m+1}\) 同理），那么 \(D_m+D_x\) 一定可以比它优。于是我们可以不用管 \(D_{m-1}\) 与其他数组合能否得到最优解，因为它一定是不能的，只要考虑 \(D_{m-1}\) 和 \(D_{m+1}\) 能否组成最优解，因为这个在 \(D_m+D_{m'}\) 里面没有考虑到。

• \(k=3\)

（k=3，它显得杂乱无章。所以我们不在乎数学的严谨性，直接讨论我们想看到的）

现在已经选出 \(k=2\) 的情况，假设如下图所示

令 \(k=2\) 中选出来的分别是 \(D_{m-1},D_{m+1}\) （和上图一样，他们 “间接相邻”）

那么决策集合也只有两个部分：1.选 \(D_{m-2}+D_{m}+D_{m+2}\)；2.选 \(D_{m-1}+D_{m+1}+D_{m'}\)（\(D_{m'}\) 就是不干扰这两个点的最小的一个点）

直观地来说，要么选蓝色部分，要么选红色部分 + \(D_{m'}\)

如果你还是不理解的话，继续解释：如果我选了蓝色部分的一个点 \(D_b\) (blue)，那么就要干扰一个甚至多个点，***扰的点记为 \(D_r\) (red)，将它更换为其他的点 \(D_e\) (else)，因为其他部分没有变化，因为有 \(D_e+D_r < D_e+D_b\)，那么我们会发现这样选取是不可行的！如果干扰了多个点（最多为两个），记为 \(D_{r1},D_{r2}\) ，将它更换为其他的点 \(D_{e1},D_{e2}\)，假设 \(D_{e1}+D_{e2}+D_b<D_{r1}+D_{r2}+D_{m'}\) 因为 \(D_{e1}>=D_{m'}\)，那么 \(D{e_2}+D_b<D_{r1}+D_{r2}\)，如此一来，这不是说明 \(D_{r1},D_{r2}\) 不是上一轮的最优解！？这与条件相矛盾，故不成立。

做出以上分析后，我们摸索出来一个性质：（先上一张图，假设当前选了 \(k\) 对点了）

如果有一些点 “间接相邻”，若有一个点***扰（选了一个蓝色点），所有的点改变位置（红色变蓝***域），形象地解释为：“同生死，共进退”。首先这个性质是我们通过刚才这些分析猜出来的，对于任意情况，可以用我给出来的这种方法做类似分析，这样证明是不是严谨的就不知道了，但是这个结论是可以证明的，具体我也不会、、

当然你还会想啊，我们选的点是离散的呀，比如下面这张图

但是对于间接相邻的这些点 上面这个性质成立呀！qwq

现在也许你对这个算法的思想大概明白了，却不知道怎么实现，这就要引出我们 “妙” 的代码实现了

• 开一个小根堆，结点存放 \(val,pos\) ，开一个链表。\(pos\) 表示这个结点在链表中相应的位置。

• 然而这个 \(val\) 就妙了，，，先讲实现流程：

• 每次从堆中取出一个结点，将 \(ans+=val\)，将链表中 \(pos,L[pos],R[pos]\) 中三个结点删去，加入在这个位置加入一个新的结点，这个新结点的 \(val=val(L[pos])+val(R[pos])-val(pos)\)，再把这个结点加入堆。结合“红蓝点的说法”，其实我们是把蓝点区域看成一种状态加入进了堆,val是记录红点区域和蓝点区域的差值（自己模拟一下会有一点点 容斥般巧妙的感觉qwq）。

• 重复 \(k\) 次得到答案。

还有 一点点细节，如果我们遇到下面这种情况：

红点在边缘，我把它叫做 “蓝点会溢出”，这种情况我们肯定不能再将蓝点区域放入堆里面了。反过来，我们不取出它就可以了。有一个小 \(Trick\)，将链表的头尾（虚拟）结点的 \(val=INF\) 即可。

综上所述，这题考察了我们 优先队列+双向链表 的灵活运用。

Code

Talk is cheap.Show me the Code.

#include<bits/stdc++.h>
#define int long long
#define INF 1e18
using namespace std;
inline int read() {
    int x=0,f=1; char ch=getchar();
    while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); }
    return x * f;
}
const int N = 100007;
int n,K,ans;
int D[N],L[N],R[N],val[N];
bool vis[N];
priority_queue<pair<int,int> > q;
signed main()
{
    n = read(), K = read();
    int last = read();
    for(int i=2,x;i<=n;++i) x = read(), D[i-1] = x-last, last = x;
    for(int i=1;i<n;++i) val[i] = D[i], L[i] = i-1, R[i] = i+1, q.push(make_pair(-val[i],i));
    val[0] = val[n] = INF;
    for(int i=1;i<=K;++i) {
        while(vis[q.top().second]) q.pop();
        int x = -q.top().first, pos = q.top().second; q.pop();
        //printf("x = %d\n",x);
        ans += x; int l = L[pos], r = R[pos];
        L[pos] = L[l], R[pos] = R[r];
        R[L[pos]] = pos, L[R[pos]] = pos;
        vis[l] = vis[r] = 1;
        val[pos] = val[l] + val[r] - x;
        //printf("updata x = %d\n",val[pos]);
        q.push(make_pair(-val[pos],pos));
    }
    printf("%lld\n",ans);
    return 0;
}

Summary

这是一道思维题，我还是要强行在这中间学到套路(逃:

• 善于从简单的情况入手，考虑数学归纳法，从而猜出一些性质

• 灵活运用双向链表，灵活实现代码（双向链表真是一种神奇的数据结构）