vegetable

用户名：xx101

访问量：1939

签　名：

等　　级
排　　名	2344
经　　验	2349
参赛次数	1
文章发表	4
年　　龄	0
在职情况	学生
学　　校	武软
专　　业

　　自我简介：

TA的其他文章

题目 3155: 蓝桥杯2023年第十四届省赛真题-整数删除
浏览：84

你可能喜欢

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

题目 3155: 蓝桥杯2023年第十四届省赛真题-整数删除

　　作者: vegetable　　　　发表时间：2023-06-07 15:27:29 浏览：84　|　评论：0　

```java
import java.util.*;
//双向链表的节点
class ListNode{
    //指向前一个节点
    public ListNode prev;
    //指向后一个节点
    public ListNode next;
    //节点的数值
    public long val;
    //节点对应数据的初始位置
    public int pos;
    public ListNode(ListNode prev,ListNode next,long val,int pos) {
        this.prev = prev;
        this.next = next;
        this.val = val;
        this.pos = pos;
    }
}
public class Main {
    //双向链表头
    static ListNode head;
    static int N,K;
    //优先队列
    static PriorityQueue<ListNode> heap;
    /*
     优先队列维护每个值和其对应的下标，并且双链表储存整个区间。
     因为每次取出的最小值，其相邻的元素要加上这个最小值，
     但是队列中无法取出，所以用 arr 数组记录每个元素需要增加的值。

每次取出队头的元素，如果这个 arr 数组中没有记录这个元素，则从链表中删除，
     并且 arr 记录其相邻元素所要增加的元素。

如果 arr 中记录了这个元素，则加上 arr 中记录的增加值，然后放回队列中。
     */
    static long[] arr;
    public static void main(String[] args) {

Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        K = sc.nextInt();
        arr = new long[N];

//优先队列排序规则，先val比较再pos比较
        heap = new PriorityQueue<>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                if(o1.val == o2.val) {
                    if(o1.pos>o2.pos) {
                        return 1;
                    }else if(o1.pos<o2.pos){
                        return -1;
                    }else {
                        return 0;
                    }
                }else if(o1.val>o2.val) {
                    return 1;
                }else { //o1.val<o2.val
                    return -1;
                }
            }
        });

//构建双向链表
        head = new ListNode(null,null,-1,0);
        ListNode firstNode = new ListNode(head,null,sc.nextInt(),0);
        head.next = firstNode;
        ListNode curPrev = firstNode;
        //第一个数放入优先队列
        heap.offer(firstNode);

for(int i=0;i<N-1;i++) {
            //双向链表插入节点
            ListNode cur = new ListNode(curPrev,null,sc.nextInt(),i+1);
            curPrev.next = cur;
            curPrev = cur;
            //优先队列插入节点
            heap.offer(cur);
        }
        //K次操作
        doK(head);
        //显示链表全部节点
        showAll(head);
    }

public static void showAll(ListNode listHead) {
        ListNode cur = listHead.next;
        while(cur!=null) {
            cur.val += arr[cur.pos];
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
    }

public static void doK(ListNode listHead) {
        while(K>0) {
            //取优先队列头节点
            ListNode minNode = heap.poll();
            //如果存在加值
            if(arr[minNode.pos]>0){
                //节点数值加上加值
                minNode.val += arr[minNode.pos];
                //对应位置加值清零
                arr[minNode.pos] = 0;
                //重新入优先队列
                heap.offer(minNode);
            }else {
                //最小值节点左右位置设置加值
                if (minNode.prev != head) {
                    arr[minNode.prev.pos] += minNode.val;
                }
                if (minNode.next != null) {
                    arr[minNode.next.pos] += minNode.val;
                }
                //删除最小值节点
                if (minNode.next != null) {
                    minNode.next.prev = minNode.prev;
                }
                minNode.prev.next = minNode.next;
                K--; //每次删除最小值节点算完成一次K操作
            }
        }
    }
}

```

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

vegetable

TA的其他文章

你可能喜欢

【亲和数】（C语言代码）

C二级辅导-温度转换（C++代码）

【矩阵】（C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

题目 3155: 蓝桥杯2023年第十四届省赛真题-整数删除

评论区

精彩推荐

不需要数组和指针的做法！！！

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C++代码）（其实不需要开数组，一个一个字符读入并判断就好了）

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

C语言程序设计教程（第三版）课后习题9.4 （C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

破解简单密码（C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

vegetable

TA的其他文章

你可能喜欢

【亲和数】 （C语言代码）

C二级辅导-温度转换 （C++代码）

【矩阵】 （C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

题目 3155: 蓝桥杯2023年第十四届省赛真题-整数删除

评论区

精彩推荐

不需要数组和指针的做法！！！

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C++代码）（其实不需要开数组，一个一个字符读入并判断就好了）

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

C语言程序设计教程（第三版）课后习题9.4 （C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

破解简单密码 （C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

【亲和数】（C语言代码）

C二级辅导-温度转换（C++代码）

【矩阵】（C语言代码）

　　评论区

破解简单密码（C语言代码）