思路分析

• 这道题有很强的一种性质，就是选的两个点之间连边的话一定是相邻的，假如不相邻，一定不是最优。
• 把每两个点之间的距离求出，等价于找到k个互不相邻的点，使得总和最小。
• 假如只有两次选择，第一次肯定就是选择当前最小的值，第二次要么选择与最小值不相邻中的最小值，第二种就是把最小值去掉选择最小值两边的值。
  • 为什么是对的？假如我们只选最小值其中一边的值，另一个选择其他点，那么一定不如选择最小值最优，假如选择最小值，那么另一个点一定是与最小值不相邻的最小值，因此最小值两边的值要么全选，要么全部选。
• 怎么维护？可以看出要维护最小值，那么就要用小根堆，还要维护当前值两边的值是那些，因此要用双链表。