题解 P3620 【[APIO/CTSC 2007]数据备份】（贪心，二叉堆）
RyexAwl
2020-05-06 02:06:25
#### [更好的阅读体验](https://www.cnblogs.com/wxy-max/p/12834098.html)
---
# 暴力
## 思路
首先这道题有一个极为明显的性质：要使每段最短，只能使其这一段只经过两个端点，中间不经过任何建筑。
因此我们可以通过这个性质，枚举每组可行方案，最后选出长度前$k$小的方案。
## 复杂度分析
因为一共有$n$个建筑，存在$n-1$个间隔，每个间隔都有选或不选的两种可能，因此暴力枚举的复杂度为$O(2^n)$。
# 正解（贪心）
## 思路
我们从题目给出的样例开始手玩。
如图，定义$F[i]$为第$i$个间隔的距离。
那么很显然，如果我们要想让当前方案的距离总和尽可能小，肯定要优先选当前距离最小的。我们定义$F[u]$为集合$F$中最小的元素。
那么我们是不是可以每次选取我们能选的最小的元素呢？根据样例来看很显然是不可能的，因为你能选的最小的元素可能非常大，远大于$F[u-1]$与$F[u+1]$。
而根据给出的样例，我们选中的两个元素全局最小值$F[u]$两边的元素$F[u-1]$与$F[u+1]$。那么很显然我们就有了以下几种选择方法：
1.选择全局最小值$F[u]$，与除了$F[u-1]$和$F[u+1]$的全局最小值。
2.选择全局最小值$F[u]$两边的元素其中一个$F[u-1]$或$F[u+1]$并选取其他元素使其尽量小。
而对于方案二来说，如果我们要让方案而的状态空间进一步缩小，即让其状态空间所包括的元素尽量少并不遗漏所可能是答案的元素，那么选取了$F[u-1]$，那么我们就一定要选取$F[u+1]$，反之亦是如此，而不能在其他元素中“找小三”。
为什么？
因为如果我们选取了$F[u-1]$与一个元素$F[a]$，那么必然有$F[a] + F[u] < F[u-1]+F[u]$，而对于$F[u+1]$也是如此。
#### 即最小值两侧的点要么全选，要么全不选。
所以，如果我们选择了$F[u+1]$与$F[u-1]$中的任意一个，我们必须选择其令一个才能使其状态空间尽量小，复杂度尽量优。
那么对于$k=2$我们就推出了两种基本的选法：
1.选择全局最小值$F[u]$，与除了$F[u-1]$和$F[u+1]$的全局最小值。
2.选择全局最小值$F[u]$两边的元素$F[u+1]$与$F[u-1]$。
那么我们就可以通过比较$F[u]$与合法的全局最小值$F[v]$的和$F[u]+F[v]$与$F[u+1]+F[u-1]$的答案来得到答案。
那么我们这种思路能否推广到$k>2$的情况呢？
我们可以先找到全局最小值$F[u]$，维护一个集合$S$，将$F[u-1]+F[u-1]$与$F$集合中除了$F[u]$ $F[u-1]$及$F[u+1]$以外的元素与$F[u]$相加后加入集合维护，并将问题转化为“求解从$F$集合中选出不超过$K-1$个数，使其和最小”。
而我们如果选择了$F[u+1]+F[u-1]$这个状态说明我们目前选择的最优答案中不包括$F[u]$,将答案更新为$F[u+1]+F[u-1]$如果选择了$F[v]$，则将$F[v]$更新为答案。而如果是前者，我们则需要将$S$集合中的元素全都更新为$F[u+1]+F[u-1]+F[i]$，而对于这个状态而言我们同样有两种选择，我们可以选择合法的最小的$F[v]$或者选择$F[u-2]$,$F[u]$，与$F[u+2]$，因此我们可以将$F[u-2]$,$F[u]$与$F[u+2]$一同加入集合$S$维护。而对于后者，我们的选择方案同样为$F[u]+F[u+2]$与$F[v]$。
而其中$F$集合因为我们要快速地找出并修改某个元素前面的元素的前面的元素与后面的元素，所以我们可以使用链表维护，而$S$集合要快速找出最小的元素，所以可以用小根堆维护。
因此，我们可以初始化$ans=0$，$F$,$S$（全部元素均加入到$F$与$S$集合），每次将堆顶取出加到$ans$，并在链表中移除堆顶所对元素与堆顶所对元素的前驱与后继，在堆中移除堆顶所对应的前驱与后继。将堆顶的前驱与后继的和减去堆顶的值插入堆中维护，并在链表中插入元素，其前驱为堆顶所对元素的前驱的前驱，后继为堆顶所对元素后继的后继。重复$k$次得到的就为答案。
## 复杂度分析
初始化链表的复杂度为$O(n)$，初始化二叉堆的复杂度为$O(n\ log\ n)$。
而链表与堆中的每个元素最多进$n$次删$n$次，因此总的复杂度为$O(n\ log\ n)$
## 代码
```cpp
#include<iostream>
#include<cstdio>
using namespace std;
int f[100010],a[100010],pre[100010],next[100010],v[100010];
int n,m,p,i,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 insert(int x)
{
f[++p]=x; v[x]=p;
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;
for(i=1;i<=n;i++) scanf("%d",&a[i]);
for(i=1;i<n;i++)
{
a[i]=a[i+1]-a[i];
next[i]=i+1,pre[i+1]=i;
insert(i);
}
for(i=1;i<=m;i++)
{
x=f[1]; ans+=a[x];
if(pre[x]==0&&next[x]==n) break;
if(pre[x]==0)
{
erase(x),erase(next[x]);
pre[next[next[x]]]=0;
}
else if(next[x]==n)
{
erase(x),erase(pre[x]);
next[pre[pre[x]]]=n;
}
else{
erase(x),erase(pre[x]),erase(next[x]);
a[x]=a[pre[x]]+a[next[x]]-a[x];
insert(x);
pre[x]=pre[pre[x]]; next[pre[x]]=x;
next[x]=next[next[x]]; pre[next[x]]=x;
}
}
cout<<ans<<endl;
return 0;
}
```