题目描述
你在一家IT公司为大型写字楼或办公楼的计算机数据做备份。
然而数据备份的工作是枯燥乏味的,因此你想设计一个系统让不同的办公楼彼此之间互相备份,而你则坐在家中尽享计算机游戏的乐趣。
已知办公楼都位于同一条街上,你决定给这些办公楼配对(两个一组)。
每一对办公楼可以通过在这两个建筑物之间铺设网络电缆使得它们可以互相备份。
然而,网络电缆的费用很高。
当地电信公司仅能为你提供 K 条网络电缆,这意味着你仅能为 K 对办公楼(总计2K个办公楼)安排备份。
任意一个办公楼都属于唯一的配对组(换句话说,这 2K 个办公楼一定是相异的)。
此外,电信公司需按网络电缆的长度(公里数)收费。
因而,你需要选择这 K 对办公楼使得电缆的总长度尽可能短。
换句话说,你需要选择这 K 对办公楼,使得每一对办公楼之间的距离之和(总距离)尽可能小。
下面给出一个示例,假定你有 5 个客户,其办公楼都在一条街上,如下图所示。
这 5 个办公楼分别位于距离大街起点 1km, 3km, 4km, 6km 和 12km 处。
电信公司仅为你提供 K=2 条电缆。
上例中最好的配对方案是将第 1 个和第 2 个办公楼相连,第 3 个和第 4 个办公楼相连。
这样可按要求使用 K=2 条电缆。
第 1 条电缆的长度是 3km-1km=2km ,第 2 条电缆的长度是 6km-4km=2km。
这种配对方案需要总长 4km 的网络电缆,满足距离之和最小的要求。
样例
输入样例:
5 2
1
3
4
6
12
输出样例:
4
算法1
(贪心+双向链表) $O(nlogn)$
首先可以证明
如果第k次取蓝色部分,那么第k+1取的部分一定不包含红色部分,即取的是蓝色部分。
证明:
如果第k + 1次取了蓝色部分中的一个, 那么蓝色部分中的一个,可以往k - 1次中的一个变化,使得结果更小。
考虑如何计算每次取的值。如图
有些这些铺垫后,算法主要思想:
1.由于需要对堆中的数据进行修改,所以采用set
存储
2.将n个值insert
到set
里面
3.每次取出set
的头部,然后删除相邻的边(根据题目要求,相邻边不能取)
4.在set
中插入删除的两条边的和。(因为这两条相邻边也有可能达到最小值)放在第4步加的原因,因为下一轮循环可能会取到,(妙妙妙!)
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
const int N = 100010;
typedef long long LL;
typedef pair<LL, int> PLI;
int n, k;
int l[N], r[N];
LL d[N];
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];
set<PLI> s;
d[0] = d[n] = 1e15;
for (int i = 0; i <= n; i ++){
l[i] = i - 1;
r[i] = i + 1;
s.insert({d[i], i});
}
LL res = 0;
while (k --){
auto it = s.begin();
LL v = it->first;
int p = it->second, 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;
return 0;
}