四倍经验（1蓝2紫1黑）：P3620，SP1553，P1484，P1792
题意
将 $N$ 个办公楼两两配成 $K$ 对，要求这 $K\times 2$ 栋楼相异。所有办公楼在一条直线上，配对的两栋楼之间需要连接电缆，求电缆长度的最小值。
$N\le 100000$ 。
题解
显然，配对相邻的两栋楼是最优的。将边看成点来考虑，题目即转化成：在 $N$ 个点中选 $K$ 个不相邻的点，使得点权最小。
每次选点的最优策略只有两种：
- 选最小的点
- 把最小的点左右两侧的点都选上
如果不选最小的点，在左右两侧只选一个的话显然是不如直接选最小点的。
实现就是每次取最小的点 $S_i$ ，把该点的值替换为 $S_{i-1}+S_{i+1}-S_i$ ，并把它左右节点删除。如果后续又选到的这个点，就相当于最初选了左右两侧的点。
删除就用数组模拟链表，并记录哪些点被删就行了。
#include<bits/stdc++.h>
#define pr pair<int,int>
#define mp make_pair
using namespace std;
inline int read()
{
char ch=getchar();
int f=1,x=0;
while (ch<'0' || ch>'9')
{
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0' && ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return f*x;
}
bool d[100005];
int n,k,ans,s[100005],l[100005],r[100005];
priority_queue <pr,vector<pr>,greater<pr> > q;
inline void del(int x) //删除点
{
d[x]=1;
l[r[x]]=l[x];
r[l[x]]=r[x];
}
signed main()
{
n=read(); k=read();
for (int i=1;i<=n;i++) s[i]=read();
for (int i=1;i<n;i++) s[i]=s[i+1]-s[i],l[i]=i-1,r[i]=i+1;
s[0]=s[n]=1e9;
for (int i=1;i<n;i++) q.emplace(mp(s[i],i));
for (int i=1;i<=k;i++)
{
int x=q.top().first,y=q.top().second; q.pop();
if (d[y]) { i--; continue; } //被删则跳过
ans+=x;
s[y]=s[l[y]]+s[r[y]]-s[y];
q.emplace(mp(s[y],y));
del(l[y]); del(r[y]);
}
return !printf("%d",ans);
}