2020-01-02 12:42 湖南省醴陵第一中学算法工程师

关注

[算进] 数据备份

数据备份

https://ac.nowcoder.com/acm/contest/1011/C

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;
}