题解：学而思编程 x轴最大距离

张开发
• 2026/4/19 9:02:29 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

题解：学而思编程 x轴最大距离
本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】x轴最大距离【题目描述】考虑x轴上的点组成的集合S SS你需要写一个数据结构支持以下操作1 x添加一个坐标为x xx的点到集合S SS中。2- n删除第n nn次添加的点添加操作按顺序从1 11编号其他操作不参与计数。3? x计算S SS集合中与x xx的距离最大的点的距离保证询问时集合S SS中至少有一个点。两个点x 1 x_1x1​和x 2 x_2x2​的距离等于坐标之差的绝对值∣ x 1 − x 2 ∣ |x_1−x_2|∣x1​−x2​∣。【输入】第1 11行1 11个正整数Q QQ表示操作的总数。接下来Q QQ行每行包含一条操作。【输出】对每个询问操作输出最大的距离。【输入样例】5 8 -1 ? 5 - 2 ? -100【输出样例】6 108【算法标签】#堆排序#【代码详解】#includebits/stdc.husingnamespacestd;constintN200005;structNode{intid,v;// id: 元素编号, v: 元素值};priority_queueNodeq1;// 大根堆priority_queueNode,vectorNode,greaterNodeq2;// 小根堆// 定义大根堆的比较操作booloperator(Node x,Node y){returnx.vy.v;}// 定义小根堆的比较操作booloperator(Node x,Node y){returnx.vy.v;}intq,cnt;// cnt: 元素计数器boolf[N];// 标记元素是否被删除intmain(){cinq;while(q--){charop;intx;cinopx;if(op){cnt;q1.push(Node{cnt,x});// 插入大根堆q2.push(Node{cnt,x});// 插入小根堆}elseif(op?){// 清理堆顶已被删除的元素while(f[q1.top().id]true){q1.pop();}while(f[q2.top().id]true){q2.pop();}// 计算最大值intmaxnmax(q1.top().v-x,x-q2.top().v);coutmaxnendl;}else{f[x]true;// 标记删除}}return0;}【运行结果】5 8 -1 ? 5 6 - 2 ? -100 108

更多文章