【题目大意】
有$n$座房子在一条街上，给出每座房子距起点的距离，现在有$k$根电缆可以把两个房子连接起来。保证每座房子至多只会与一座房子相连，求最短的电缆总长度。
【思路分析】
相当于看成$n-1$个物品，每个物品有一个权值(即两座房子之间的距离)，要求不能取相邻的物品，求取出$k$个物品的最小权值之和。
我们用一个堆将这$n-1$个物品从小到大排序，堆顶为权值最小的。假设现在取了堆顶的物品$a_i$，如果我们同时选$a_{i-1},a_{i+1}$才有可能更优，如果单选$a_{i-1}$或$a_{i+1}$一定不会更优，因为$a_i$在堆顶就已经保证了$a_i$是当前最小值。如果不选$a_i$而改选$a_{i-1}$和$a_{i+1}$，那么总答案加上$a_{i-1}+a_{i+1}-a_i$，此时我们可以把堆中的$a_{i-1}$和$a_{i+1}$删除，插入一个权值为$a_{i-1}+a_{i+1}-a_i$的新物品，同时更新链表的值，把$a_{i-1},a_i,a_{i+1}$当作一个物品处理。
【代码实现】
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #include<queue> 7 #define g() getchar() 8 #define rg register 9 #define go(i,a,b) for(rg int i=a;i<=b;i++) 10 #define back(i,a,b) for(rg int i=a;i>=b;i--) 11 #define db double 12 #define ll long long 13 #define il inline 14 #define pf printf 15 using namespace std; 16 ll fr(){ 17 ll w=0,q=1; 18 char ch=g(); 19 while(ch<‘0‘||ch>‘9‘){ 20 if(ch==‘-‘) q=-1; 21 ch=g(); 22 } 23 while(ch>=‘0‘&&ch<=‘9‘) w=(w<<1)+(w<<3)+ch-‘0‘,ch=g(); 24 return w*q; 25 } 26 const int N=100002; 27 const int INF=1e9+7; 28 ll n,k,a[N],L[N],R[N],s[N],ans;//L,R记录链表位置 29 bool vis[N]; 30 struct node{ 31 int id;ll data; 32 }p; 33 priority_queue<node> q;//用堆维护一下 34 il bool operator < (node x,node y){return x.data>y.data;}//重载运算符 35 int main(){ 36 //freopen("","r",stdin); 37 //freopen("","w",stdout); 38 n=fr();k=fr(); 39 go(i,0,n-1){ 40 s[i]=fr(); 41 if(i){ 42 p=(node){i,a[i]=s[i]-s[i-1]}; 43 q.push(p); 44 L[i]=i-1;R[i]=i+1; 45 } 46 } 47 R[0]=1;L[n]=n-1;a[0]=a[n]=INF; 48 while(k--){ 49 while(vis[q.top().id]) q.pop(); 50 node t=q.top();q.pop(); 51 rg int pos=t.id; 52 ans+=t.data; 53 t.data=a[pos]=a[L[pos]]+a[R[pos]]-a[pos]; 54 q.push(t); 55 vis[L[pos]]=vis[R[pos]]=1; 56 L[pos]=L[L[pos]];R[pos]=R[R[pos]]; 57 R[L[pos]]=L[R[pos]]=pos; 58 } 59 pf("%lld\n",ans); 60 return 0; 61 }
原文：https://www.cnblogs.com/THWZF/p/11545553.html
