题目 T46773.【贪心算法(二)】跳跃游戏 T46772.【贪心算法(二)】柠檬水找零 T46771.【贪心算法(二)】纪念品分组 T48915.【贪心算法(二)】老鼠吃奶酪 A605. 入栈出栈 T46399.模拟栈操作 T46400.表达式括号匹配 A670. 模拟队列操作 A29683. 发牌游戏【队列】
T46773.【贪心算法(二)】跳跃游戏
题目大意
给定一个长度为 nnn 的数组 aaa,每个元素 aia_iai 表示从当前位置最多可以向前跳跃的步数。初始站在下标 000,问是否能跳到下标 n−1n - 1n−1,如果可以,输出 true,否则输出 false。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
这道题目本质是一个可达性判断问题,我们希望知道:在跳跃范围有限的情况下,从起点出发,能否“一级级跳”到终点。
关键点是:在走到第 iii 个位置时,判断是否能够到达 iii,如果能,就尝试更新最远可以跳到的位置。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
采用贪心策略,维护一个变量 maxReach 表示当前为止能跳到的最远位置。
* 初始设 maxReach = 0;
* 从左到右遍历每个位置 iii:
* 如果当前位置 i>maxReachi > \text{maxReach}i>maxReach,说明当前位置无法跳到,直接返回 false;
* 否则,用 i+aii + a_ii+ai 更新 maxReach;
* 遍历结束后,判断 maxReach≥n−1maxReach \geq n - 1maxReach≥n−1 即可。
这种策略是贪心的,因为我们每次总是向前扩展跳跃的最远位置。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度解析
算法仅需线性扫描一遍数组
时间复杂度为:O(n)\mathcal{O}(n)O(n)
空间复杂度为:O(1)\mathcal{O}(1)O(1)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码演示
T46772.【贪心算法(二)】柠檬水找零
题目大意
有一个柠檬水摊,每杯柠檬水售价为 555 元。每位顾客排队购买,每人只买一杯,支付的金额可能是 555、101010 或 202020 元。你需要在一开始没有任何零钱的前提下,判断是否可以给每位顾客找零成功。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
本题是一个典型的贪心问题。
我们需要按顺序处理每一位顾客的支付:
* 如果顾客付 555 元:无需找零;
* 如果顾客付 101010 元:需要找 555 元;
* 如果顾客付 202020 元:优先找一张 101010 元和一张 555 元,其次找三张 555 元。
我们需要贪心地优先使用大额钞票找零,以便保留更多的小额纸币。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
设变量:
* cnt5:当前拥有的 555 元纸币数量;
* cnt10:当前拥有的 101010 元纸币数量;
按照顾客支付的金额分类处理:
1. 若支付 555,增加 cnt5;
2. 若支付 101010:
* 若有 555 元,则找零,cnt5--,cnt10++;
* 否则失败;
3. 若支付 202020:
* 优先选择:cnt10 > 0 && cnt5 > 0,则分别减 111;
* 否则尝试 cnt5 >= 3,减 333;
* 否则失败。
任何一步失败,立即输出 false;全部处理完毕输出 true。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度解析
每位顾客处理一次,常数操作:
O(n)\mathcal{O}(n)O(n)
空间复杂度为:
O(1)\mathcal{O}(1)O(1)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码演示
T46771.【贪心算法(二)】纪念品分组
题目大意
给定一个正整数上限 www,和 nnn 件纪念品,每件纪念品有一个价格 PiP_iPi 。要求把这些纪念品分成若干组,每组最多两件,且每组内纪念品价格之和不能超过 www。求最少可以分成多少组。
题意分析
每组最多包含两件纪念品,且价格之和不得超过 www,目标是使分组数最少,这意味着要尽量多地将两个纪念品放到同一组中。
解题思路
该题可以使用 双指针 + 贪心算法 来解决:
1. 首先对所有纪念品按价格从小到大排序。
2. 设置两个指针:
* 左指针 iii 指向价格最低的纪念品。
* 右指针 jjj 指向价格最高的纪念品。
3. 若 Pi+Pj≤wP_i + P_j \leq wPi +Pj ≤w,说明可以将这两个纪念品分为一组,分组数加一,左右指针同时移动。
4. 若不能组合,说明价格最高的那个纪念品必须单独一组,将右指针左移。
5. 重复以上操作直到指针交叉。
这个策略保证每次都尽可能让两个纪念品成组,从而减少组数,是一种典型的贪心策略。
时间复杂度解析
* 排序部分:O(nlogn)O(n \log n)O(nlogn)
* 双指针遍历:O(n)O(n)O(n)
* 总体时间复杂度:O(nlogn)O(n \log n)O(nlogn),可以通过数据范围 n≤3×104n \leq 3 \times 10^4n≤3×104
代码演示
T48915.【贪心算法(二)】老鼠吃奶酪
题目大意
有两只老鼠 aaa 和 bbb,以及 nnn 块不同类型的奶酪。
每块奶酪只能被一只老鼠吃掉:
* 如果奶酪 iii 被老鼠 aaa 吃掉,获得 aia_iai 分;
* 如果被老鼠 bbb 吃掉,获得 bib_ibi 分。
要求让老鼠 aaa 恰好吃掉 kkk 块奶酪,使得 两只老鼠的总得分最大。
求该最大得分。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
每块奶酪只能选一次,且必须分配给老鼠 aaa 或 bbb。
由于老鼠 aaa 必须恰好吃 kkk 块,我们不能暴力枚举所有 C(n,k)C(n, k)C(n,k) 种组合。我们需要一个高效的贪心策略来判断哪些奶酪更适合给老鼠 aaa。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
差值排序 + 贪心
对于每一块奶酪 iii,我们定义其给老鼠 aaa 比给老鼠 bbb 更划算的程度为:
ci=ai−bic_i = a_i - b_ici =ai −bi
然后按 cic_ici 从大到小排序,表示“更应该被 aaa 吃”的优先级。
策略如下:
* 选择前 kkk 个 cic_ici 最大的奶酪给老鼠 aaa 吃;
* 剩下的 n−kn - kn−k 块给老鼠 bbb 吃;
* 这样在满足 aaa 恰好吃 kkk 块的条件下,总得分最大。
为什么正确?
这是典型的贪心选择原理。每块奶酪的“增益”就是 ai−bia_i - b_iai −bi :
* 当 cic_ici 越大,意味着越应该由 aaa 吃;
* 选取 kkk 个最大 cic_ici 即可。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度分析
* 计算差值 cic_ici :O(n)O(n)O(n);
* 排序 cic_ici :O(nlogn)O(n \log n)O(nlogn);
* 累加前 kkk 个 aia_iai ,后 n−kn - kn−k 个 bib_ibi :O(n)O(n)O(n);
总时间复杂度为:O(nlogn)\boxed{O(n \log n)}O(nlogn)
在 n≤1000n \le 1000n≤1000 的范围内完全可接受。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码演示
A605. 入栈出栈
题目大意
给定一个长度为 nnn 的整数序列,表示这 nnn 个数按照给定顺序依次入栈(即先后调用 pushpushpush 操作),求它们全部入栈后再逐个出栈时的出栈序列。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
由于栈是**后进先出(LIFO)**的数据结构:
* 第一个入栈的元素会最后出栈;
* 最后一个入栈的元素会最先出栈。
因此,本题本质就是:将输入序列反过来输出即可。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
1. 将所有输入的整数按顺序压入栈;
2. 然后从栈中依次弹出元素并输出,即为出栈序列。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度分析
* 入栈操作:O(n)O(n)O(n);
* 出栈操作:O(n)O(n)O(n);
* 总时间复杂度:O(n)\boxed{O(n)}O(n) ;
* 空间复杂度为 O(n)O(n)O(n)(栈的大小)。
由于 n<100n < 100n<100,该方法在时空范围内完全安全。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码演示
T46399.模拟栈操作
题目大意
模拟一个栈的数据结构,支持以下 555 种操作:
1. push x:将整数 xxx 压入栈;
2. pop:弹出栈顶元素,若成功输出 pop x,否则输出 pop fail;
3. top:查看栈顶元素,若成功输出 top = x,否则输出 top fail;
4. size:输出当前栈内元素个数 size = x;
5. empty:判断栈是否为空,输出 yes 或 no。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
本题是典型的栈的模拟题,难度不高,只要正确维护栈的操作和边界判断即可。
由于操作数量较小(n≤100n \le 100n≤100),不涉及任何性能优化问题,直接用标准库的 stack<int> 即可完成。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
* 使用 stack<int> 存储数据;
* 遍历每一条命令,根据命令类型执行对应逻辑;
* 对于 pop 和 top 操作需要额外判断栈是否为空,以避免访问空栈;
* 其余操作直接输出对应信息即可。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度分析
* 每次操作均为 O(1)O(1)O(1);
* 总体时间复杂度为 O(n)O(n)O(n),其中 nnn 为操作数量。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码演示
T46400.表达式括号匹配
题目大意
给定一个以 @ 结尾的数学表达式(长度不超过 255255255),表达式由小写字母、运算符 + - * /、左右圆括号 ( 和 ) 组成。
要求判断该表达式中的圆括号是否匹配,即每一个左括号 ( 都有对应的右括号 ) 与之匹配,且顺序合理。
如果匹配,输出 YES;否则输出 NO。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
本题是经典的括号匹配问题,可使用栈来实现匹配判定:
* 每遇到一个 (,将其压入栈;
* 每遇到一个 ),尝试从栈中弹出一个 (,若栈为空则说明不匹配;
* 最后若栈非空,说明还有未匹配的 (,也不合法。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
1. 遍历整个表达式,忽略所有非括号字符;
2. 用一个栈存储每一个左括号 (;
3. 遇到 ( 就入栈;
4. 遇到 ):
* 若栈非空,则弹出一个;
* 若栈为空,则立即判断不合法;
5. 表达式读完后,如果栈为空,则合法(匹配成功)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度分析
* 每个字符最多被处理一次;
* 栈操作为 O(1)O(1)O(1);
总时间复杂度为:O(n)\boxed{O(n)}O(n)
其中 nnn 为表达式长度,最大不超过 255255255。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码演示
A670. 模拟队列操作
题目大意
给定一系列队列操作,格式如下:
* 1 x:将元素 xxx 入队;
* 2:将队首元素出队;
* 3:访问队首元素,输出其值;
当遇到非法操作(即操作时队列为空)时,输出 "impossible!"。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
本题是一个标准的队列模拟题,只需要按照题意依次执行操作:
* 入队使用 q.push(x);
* 出队使用 q.pop(),前提是 q 不为空;
* 查看队首使用 q.front(),也要求队列非空。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
1. 使用 queue<int> 来模拟队列结构;
2. 遍历 nnn 次,每次读取一条指令;
3. 对于每条指令判断是否合法(是否对空队列进行非法操作);
4. 合法则执行操作并按格式输出;
5. 不合法则输出 "impossible!"。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度分析
* 每条操作均为 O(1)O(1)O(1);
* 总时间复杂度为 O(n)O(n)O(n),其中 nnn 为操作次数;
空间复杂度为 O(n)O(n)O(n)(最坏情况下队列长度为 nnn)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码演示
A29683. 发牌游戏【队列】
题目大意
小龟用 kkk 张编号为 111 到 kkk 的纸牌和 n−1n-1n−1 个朋友一起玩牌,总共 nnn 个玩家。
游戏规则如下:
1. 最开始将牌堆顶的牌(最前面的牌)发给第 111 个玩家(小龟右手边);
2. 发完一张牌后,从牌堆顶将接下来的 ppp 张牌依次移到底部;
3. 然后继续将下一张牌发给下一个人,按逆时针方向,循环进行;
4. 按上述顺序,依次输出所有发出去的纸牌编号。
输入为整数 kkk、nnn、ppp,请输出每张牌被发出的顺序编号。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
这实际上是一个队列循环模拟问题:
* 牌堆为一个队列,模拟牌的进出;
* 每次操作都遵循「发牌 + 移动 ppp 张牌到底部」的规则;
* 按照玩家的顺序发牌,每次更新发牌人指针(不影响实际模拟逻辑,只需顺序正确);
* 直到所有 kkk 张牌发完,输出其发牌顺序。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
* 初始化队列,将牌编号 111 到 kkk 依次入队;
* 用一个循环模拟发牌过程:
* 每次将队首元素弹出并输出;
* 然后将接下来的 ppp 张牌移到队列末尾(每张都是:取出队首 → 再压入队尾);
* 循环直到队列为空,即 kkk 张牌全部发出。
注意: 不需要真的模拟发给哪个人,只要按顺序处理即可。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度分析
每次操作:
* 发一张牌:O(1)O(1)O(1);
* 移动 ppp 张牌:O(p)O(p)O(p);
总共 kkk 张牌,最多执行 kkk 次发牌,每次最多执行 ppp 次额外操作:
总复杂度=O(k⋅p)\text{总复杂度} = O(k \cdot p)总复杂度=O(k⋅p)
题目范围为 k,n,p<10000k, n, p < 10000k,n,p<10000,在 O(108)O(10^8)O(108) 级别以下,仍可接受。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码演示