《数据结构实验指导-C++语言版》 爆气球

题目描述爆气球对孩子们来说是很好玩的游戏。假设有nnn只气球被布置在一条直线上游戏的目标很简单就是爆掉尽可能多的气球。但是这里我们加一条特殊的规则——你只能跳一次。我们假设聪明的娃穿了件浑身带刺的衣服跳到某个位置后躺平如下图所示这样气球只要碰到娃身体的任何部分都会立刻爆炸。那么你的任务就是告诉娃应该跳到哪里才能一次爆掉最多的气球。输入格式输入共两行第一行两个正整数nnnn≤105n \le 10^5n≤105和hhhh≤103h \le 10^3h≤103分别表示气球数量和孩子伸直双臂能达到的高度。第二行nnn个整数每个对应一只气球在直线轴上的坐标。题目保证坐标按递增顺序给出所有坐标值均在[−106,106][-10^6, 10^6][−106,106]区间内。输出格式在一行中输出孩子跳跃的位置坐标使得孩子跳到这个位置然后躺平能够爆掉身下最多的气球随后输出能爆掉的气球的最大数量。如果这个坐标不唯一输出最小的那个值。一行中的数字间应有 1 个空格行首尾不得有多余空格。**注意**跳到从 120 到140或 240 到 260 之间的任何位置都可以爆掉 5 只气球所以 120 作为最小的坐标被输出。题目引用自攀拓考试真题2022年秋季。输入样例11 120 -120 -40 0 80 122 140 160 220 240 260 300输出样例120 5解题思路孩子躺平后覆盖一个长度为hhh的闭区间[y,yh][y, yh][y,yh]落在区间内的气球都会被爆掉。问题转化为在所有长度为hhh的区间中找出能覆盖最多气球的那个并输出其左端点yyy的最小值。由于坐标已按递增顺序给出使用双指针滑动窗口在线性时间内求解固定窗口左边界为第iii只气球右指针j不断右移直到x[j]x[i]hx[j] x[i] hx[j]x[i]h窗口内气球数为j−ij - ij−i。记录最大数量的同时保存窗口最右气球的坐标bestRight跳跃位置为bestRight - h这是能覆盖该窗口所有气球的最小位置只有cnt bestCnt时才更新保证坐标不唯一时输出最小值。时间复杂度O(n)O(n)O(n)双指针各自至多移动nnn次。空间复杂度O(n)O(n)O(n)存储坐标数组。代码流程说明读入气球数量nnn和高度hhh读入所有气球坐标。对坐标排序题目保证递增排序用于保险。初始化最优数量bestCnt 0、最优右端点bestRight x[0]、右指针j 0。以每个位置i作为窗口左边界保证j i右移j直到x[j] x[i] h窗口内气球数cnt j - i若cnt bestCnt更新bestCnt和bestRight x[j-1]。输出bestRight - h跳跃位置和bestCnt。代码实现#includeiostream#includealgorithmusingnamespacestd;constintMAXN100005;intx[MAXN];intmain(){intn,h;cinnh;for(inti0;in;i)cinx[i];// 孩子躺在长度 h 的闭区间 [y, yh] 内覆盖区间内的所有气球sort(x,xn);intbestCnt0,bestRightx[0];intj0;for(inti0;in;i){if(ji)ji;while(jnx[j]x[i]h)j;intcntj-i;if(cntbestCnt){bestCntcnt;bestRightx[j-1];}}// 输出能覆盖最多气球的最小跳跃位置最优区间右端点 - 长度 hcoutbestRight-h bestCntendl;return0;}代码流程图是是否是否是否否开始读入 n, h 和气球坐标对坐标排序初始化 bestCnt, bestRight, 右指针 ji 从 0 到 n-1j 是否小于 ij 等于 i坐标 j 是否在窗口内j 加 1窗口内气球数 cnt 等于 j 减 icnt 是否大于 bestCnt更新 bestCnt 和 bestRighti 加 1输出 bestRight 减 h 和 bestCnt结束解题流程图是否是否找到爆掉最多气球的跳跃位置读入气球坐标和高度 h排序气球坐标用滑动窗口枚举长度为 h 的区间统计窗口内覆盖的气球数覆盖数是否大于当前最优更新最优覆盖数和区间是否还有窗口跳跃位置取最优区间右端点减 h输出跳跃位置和最大覆盖数