题意：
选取K对大楼，使得每对距离之和最小，并且一个大楼只会被链接一次
思路：
当k=1时肯定就是贪心的选取距离最小的那两栋。 当k=2时我们是否还要留着距离最小的那一对呢？如果没有选择距离最小的那一对，那肯定要选择最小那一对的左右两对，否则就可以将其中一对换成最小的那对，那样会更小。 当k>2时同理如果不选择中间的就必须选择其左右两边的，这样才能保证较小的那对我是因为实在拿不了的才放弃的，否则就可以更优。 我们可以用一个双指针链表加一个set来完成这些工作，当删去中间这对时将其左右两对的权值重新加入set模拟最优策略的过程；
AC代码：
#include<bits/stdc++.h>
using namespace std
;
typedef long long ll
;
const int maxn
=1e6+10;
typedef pair
<ll
,int> PLI
;
set
<PLI
> s
;
int l
[maxn
],r
[maxn
];
ll d
[maxn
];
int n
,k
;
void delete_node(int p
) {
r
[l
[p
]] = r
[p
];
l
[r
[p
]] = l
[p
];
}
int main()
{
cin
>>n
>>k
;
for(int i
=0;i
<n
;i
++) {
cin
>>d
[i
];
}
for(int i
=n
-1;~i
;i
--) {
d
[i
] -= d
[i
-1];
}
d
[0] = d
[n
] = 1e15;
for(int i
=0;i
<n
;i
++) {
l
[i
] = i
-1;
r
[i
] = i
+1;
if(i
>=1&&i
<n
) s
.insert({d
[i
],i
});
}
ll res
= 0;
while(k
--) {
auto it
= s
.begin();
ll v
= it
->first
;
int p
= it
->second
;
int left
= l
[p
],right
= r
[p
];
s
.erase(it
);
s
.erase({d
[left
],left
});s
.erase({d
[right
],right
});
delete_node(left
),delete_node(right
);
res
+=v
;
d
[p
] = d
[left
]+d
[right
]-d
[p
];
s
.insert({d
[p
],p
});
}
cout
<<res
<<endl
;
}
