AcWing 147. 数据备份(Java)
原题链接
困难
作者:
上杉
,
2021-05-14 14:06:05
,
所有人可见
,
阅读 309
注意边界问题,当最小值位于边界上时,直接将对应相邻的一并删除,不需要插入新的元素
import java.io.*;
import java.util.PriorityQueue;
/**
* @program: 算法题
* @author: 上杉
* @create: 2021-05-14 13:14
**/
public class Main {
static int n;
static int k;
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
String[] fl = bf.readLine().split(" ");
PriorityQueue<Node> heap = new PriorityQueue<>();
n = Integer.parseInt(fl[0]);
k = Integer.parseInt(fl[1]);
Node pre = null;
int preIndex = Integer.parseInt(bf.readLine());
for (int i = 1; i < n ; i++) {
int curIndex = Integer.parseInt(bf.readLine());
Node curNode = new Node(curIndex - preIndex);
preIndex = curIndex;
heap.offer(curNode);
if (pre == null){
pre = curNode;
}else {
curNode.pre = pre;
pre.next = curNode;
pre = curNode;
}
}
//1 2 4 6
//375524431
//257960899
long sum = 0;
for (int i = k; i > 0; i--) {
Node top = heap.poll();
sum += top.len;
if (i == 1){
continue;
}
Node preNode = top.pre;
Node nextNode = top.next;
if (preNode == null){
top.next.next.pre = null;
heap.remove(nextNode);
}else if (nextNode == null){
top.pre.pre.next = null;
heap.remove(preNode);
}else {
long insertVal = preNode.len + nextNode.len - top.len;
Node newNode = new Node(insertVal);
if (preNode.pre != null){
preNode.pre.next = newNode;
newNode.pre = preNode.pre;
}
if (nextNode.next != null){
newNode.next = nextNode.next;
nextNode.next.pre = newNode;
}
heap.remove(preNode);
heap.remove(nextNode);
heap.offer(newNode);
}
}
System.out.println(sum);
}
static class Node implements Comparable<Node>{
Node pre;
Node next;
long len;
public Node(long len) {
this.len = len;
}
@Override
public int compareTo(Node o) {
return len <= o.len ? -1 : 1;
}
@Override
public String toString() {
return "Node{" +
"len=" + len +
'}';
}
}
}