【bzoj1150】[CTSC2007]数据备份Backup

2014年5月7日3,6370

Description

 

Input

输入的第一行包含整数n和k,其中n(2 ≤ n ≤100 000)表示办公楼的数目,k(1≤ k≤ n/2)表示可利用的网络电缆的数目。 接下来的n行每行仅包含一个整数(0≤ s ≤1000 000 000), 表示每个办公楼到大街起点处的距离。这些整数将按照从小到大 的顺序依次出现。

Output

输出应由一个正整数组成,给出将2K个相异的办公楼连成k对所需的网络电缆的最小总长度。

Sample Input

5 2
1
3
4
6
12

Sample Output

4

HINT

上面的样例输入给出了前面描述的示例情形

对于每一个测试点,如果写到输出文件中的答案正确,则得到该测试点100%的分数,否则得零分。30%的输入数据满足n≤20。60%的输入数据满足n≤10 000。

题解

此题同2288

首先一定取的每一段都连接着相邻的楼

我们可以每次取最小的一段用堆维护

但是这样发现过不了样例,因为一栋楼只能被连接一次

考虑样例

转化为2 1 2 6中取俩个但不能相邻

在取1的时候可以加入2+2-1=3

以后取3表示不取1取两边

边界同样要考虑

比如1 2 3 4

取完1以后加入1显然是有问题的

我们其实可以直接舍弃2,可以证明无论在什么情况下,取2一定没有取1优

取2后能取的其它数取1后也能取

于是在2288的基础上随便改改就行了

快速读入飞速233