Luogu P3620 [APIO/CTSC 2007]数据备份|反悔贪心

题意：有(n)座大楼，要从中选出(k)对互异的大楼（即每座大楼仅可属于一组）接电话线。求电话线最短距离

思路：

显然的，我们应该选择相邻的大楼连电话线，否则不会最优。

由题意可知，选择了一个间隔后，相邻两个间隔将不能选择，这种限制的解法是反悔贪心的一种

下文中的点可能指点集，请读者自行理解

该解法的具体思路是
1.将点权排序
2.当我们选择一个点(a)后，将选择(a)后受限制而不能选择的点集({B})的权值-点(a)的权值（相当于合成为一点替代了(a)，下文称之为(c)）加入考虑范围，点(a)以及点集({B})退出考虑范围。

而当(c)被取出，这证明我们放弃了(a)而选择了({B})，而因为点(a)的权值被该操作抵消了，权值和也变为了选({B})而不选(a)，是正确的。当然，选择({B})后需重复操作2。从上述操作可知，点（或点集）选择后会导致相邻的点的状态可能改变。用链表维护相邻状态即可解决。

需要注意的是，边界问题会导致某些状态不合法，进而使程序WA，所以应根据实际情况，将边界设为无穷大/小

例题代码如下，代码中，“考虑范围”将用手写的小根堆维护。在代码实现中(i=1)情况不合法，(i=n+1)情况不合法，因此将(1)和(n+1)的点权设置为较大数组以保证无法取到。

#include<bits/stdc++.h>
using namespace std;
long long g,h[100100],ha[100100],p[100100],l[100100],r[100100];
bool vis[100100];int n,k,a[100100],s,sum;
void add(long long x,int xx)
{
	h[++g]=x;ha[g]=xx;
	int fa=g/2,so=g;
	while (h[fa]>h[so]&&fa)
	{
		swap(h[fa],h[so]);
		swap(ha[fa],ha[so]);
		so=fa;fa=fa/2;
	}
}
int del()
{
	int ans=ha[1];s=h[1];
	h[1]=h[g];ha[1]=ha[g];g--;
	int fa=1,so=2;
	if (h[so]>h[so+1]&&so+1<=g) so++;
	while (h[fa]>h[so]&&so<=g)
	{
		swap(h[fa],h[so]);
		swap(ha[fa],ha[so]);		
		fa=so;so*=2;
		if (h[so]>h[so+1]&&so+1<=g) so++;
	}
	return ans;
}//手写堆
int main()
{
    cin>>n>>k;
    p[1]=p[n+1]=1e17;
    for (int i=1;i<=n;i++)
    {
    	cin>>a[i];
    	if (i!=1) 
		{
			p[i]=a[i]-a[i-1];
			add(p[i],i);
		}			
		l[i]=i-1;r[i]=i+1;
    }
    for (int i=1;i<=k;i++)
    {
    	int q=del();
		{
			 if (vis[q]) {i--;continue;}
			 sum+=s;
			 vis[l[q]]=vis[r[q]]=true; //维护“延迟删除”
			 p[q]=-p[q]+p[l[q]]+p[r[q]];
			 add(p[q],q);//将上文的“点c”加入考虑范围
			 l[q]=l[l[q]];r[q]=r[r[q]];
			 l[r[q]]=q;r[l[q]]=q;//维护相邻位置
		}
    }
    cout<<sum<<endl;
	return 0;
}