有基础班_第六课_STL（栈和队列）

zxcvbnm

2025-05-25 17:07:24

发布于：上海

28阅读

0回复

0点赞

题目
T46773.【贪心算法(二)】跳跃游戏
T46772.【贪心算法(二)】柠檬水找零
T46771.【贪心算法(二)】纪念品分组
T48915.【贪心算法(二)】老鼠吃奶酪
A605. 入栈出栈
T46399.模拟栈操作
T46400.表达式括号匹配
A670. 模拟队列操作
A29683. 发牌游戏【队列】

T46773.【贪心算法(二)】跳跃游戏

题目大意

给定一个长度为 $n$ 的数组 $a$ ，每个元素 $a_i$ 表示从当前位置最多可以向前跳跃的步数。初始站在下标 $0$ ，问是否能跳到下标 $n - 1$ ，如果可以，输出 true，否则输出 false。

题意分析

这道题目本质是一个可达性判断问题，我们希望知道：在跳跃范围有限的情况下，从起点出发，能否“一级级跳”到终点。

关键点是：在走到第 $i$ 个位置时，判断是否能够到达 $i$ ，如果能，就尝试更新最远可以跳到的位置。

解题思路

采用贪心策略，维护一个变量 maxReach 表示当前为止能跳到的最远位置。

初始设 maxReach = 0；
从左到右遍历每个位置 $i$ $i$ ：
- 如果当前位置 $i > \text{maxReach}$ ，说明当前位置无法跳到，直接返回 false；
- 否则，用 $i + a_i$ 更新 maxReach；
遍历结束后，判断 $maxReach \geq n - 1$ 即可。

这种策略是贪心的，因为我们每次总是向前扩展跳跃的最远位置。

时间复杂度解析

算法仅需线性扫描一遍数组

时间复杂度为： $\mathcal{O}(n)$

空间复杂度为： $\mathcal{O}(1)$

代码演示

#include<iostream>
using namespace std;

int a[1010];

int main()
{
    int n;
    cin >> n;

    for(int i = 0; i < n; i++)
        cin >> a[i];

    int maxReach = 0;

    for(int i = 0; i < n; i++)
    {
        if(i > maxReach) break;
        maxReach = max(maxReach, i + a[i]);
    }

    if(maxReach >= n - 1)
        cout << "true";
    else
        cout << "false";

    return 0;
}

T46772.【贪心算法(二)】柠檬水找零

题目大意

有一个柠檬水摊，每杯柠檬水售价为 $5$ 元。每位顾客排队购买，每人只买一杯，支付的金额可能是 $5$ 、 $10$ 或 $20$ 元。你需要在一开始没有任何零钱的前提下，判断是否可以给每位顾客找零成功。

题意分析

本题是一个典型的贪心问题。

我们需要按顺序处理每一位顾客的支付：

如果顾客付 $5$ 元：无需找零；
如果顾客付 $10$ 元：需要找 $5$ 元；
如果顾客付 $20$ 元：优先找一张 $10$ 元和一张 $5$ 元，其次找三张 $5$ 元。

我们需要贪心地优先使用大额钞票找零，以便保留更多的小额纸币。

解题思路

设变量：

cnt5：当前拥有的 $5$ 元纸币数量；
cnt10：当前拥有的 $10$ 元纸币数量；

按照顾客支付的金额分类处理：

若支付 $5$ ，增加 cnt5；
若支付 $10$ $10$ ：
- 若有 $5$ 元，则找零，cnt5--，cnt10++；
- 否则失败；
若支付 $20$ $20$ ：
- 优先选择：cnt10 > 0 && cnt5 > 0，则分别减 $1$ ；
- 否则尝试 cnt5 >= 3，减 $3$ ；
- 否则失败。

任何一步失败，立即输出 false；全部处理完毕输出 true。

时间复杂度解析

每位顾客处理一次，常数操作：

$\mathcal{O}(n)$

空间复杂度为：

$\mathcal{O}(1)$

代码演示

#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;

    // cnt5 记录现有的 5 元钞票数量
    // cnt10 记录现有的 10 元钞票数量
    int cnt5 = 0, cnt10 = 0;

    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x; // 当前顾客支付的金额

        if (x == 5)
        {
            // 支付 5 元，不需要找零，直接收入一张 5 元
            cnt5++;
        }
        else if (x == 10)
        {
            // 支付 10 元，需要找零 5 元
            if (cnt5 == 0)
            {
                // 没有 5 元钞票，无法找零
                cout << "false" << endl;
                return 0;
            }
            // 找出一张 5 元，同时收入一张 10 元
            cnt5--;
            cnt10++;
        }
        else // x == 20
        {
            // 支付 20 元，需要找零 15 元
            if (cnt10 > 0 && cnt5 > 0)
            {
                // 优先使用一张 10 元和一张 5 元
                cnt10--;
                cnt5--;
            }
            else if (cnt5 >= 3)
            {
                // 如果没有 10 元钞票，尝试使用三张 5 元找零
                cnt5 -= 3;
            }
            else
            {
                // 无法找零
                cout << "false" << endl;
                return 0;
            }
        }
    }

    // 所有顾客都成功找零
    cout << "true" << endl;
    return 0;
}

T46771.【贪心算法(二)】纪念品分组

题目大意

给定一个正整数上限 $w$ ，和 $n$ 件纪念品，每件纪念品有一个价格 $P_i$ 。要求把这些纪念品分成若干组，每组最多两件，且每组内纪念品价格之和不能超过 $w$ 。求最少可以分成多少组。

题意分析

每组最多包含两件纪念品，且价格之和不得超过 $w$ ，目标是使分组数最少，这意味着要尽量多地将两个纪念品放到同一组中。

解题思路

该题可以使用双指针 + 贪心算法来解决：

首先对所有纪念品按价格从小到大排序。
设置两个指针：
- 左指针 $i$ 指向价格最低的纪念品。
- 右指针 $j$ 指向价格最高的纪念品。
若 $P_i + P_j \leq w$ ，说明可以将这两个纪念品分为一组，分组数加一，左右指针同时移动。
若不能组合，说明价格最高的那个纪念品必须单独一组，将右指针左移。
重复以上操作直到指针交叉。

这个策略保证每次都尽可能让两个纪念品成组，从而减少组数，是一种典型的贪心策略。

时间复杂度解析

排序部分： $O(n \log n)$
双指针遍历： $O(n)$
总体时间复杂度： $O(n \log n)$ ，可以通过数据范围 $n \leq 3 \times 10^4$

代码演示

#include <iostream>
#include <algorithm>
using namespace std;

int arr[30010];  // 存储纪念品价格

int main() {
    int w, n;
    cin >> w >> n;

    // 读取纪念品价格
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }

    // 从小到大排序
    sort(arr + 1, arr + n + 1);

    int i = 1;      // 左指针
    int j = n;      // 右指针
    int sum = 0;    // 记录分组数量

    while (i <= j) {
        if (i == j) {
            // 只剩一件纪念品，单独分一组
            sum++;
            break;
        }

        if (arr[i] + arr[j] <= w) {
            // 如果可以成对分组
            i++;
            j--;
        } else {
            // 否则右边的单独一组
            j--;
        }

        // 每次操作都对应一个分组
        sum++;
    }

    cout << sum << endl;
    return 0;
}

T48915.【贪心算法(二)】老鼠吃奶酪

题目大意

有两只老鼠 $a$ 和 $b$ ，以及 $n$ 块不同类型的奶酪。

每块奶酪只能被一只老鼠吃掉：

如果奶酪 $i$ 被老鼠 $a$ 吃掉，获得 $a_i$ 分；
如果被老鼠 $b$ 吃掉，获得 $b_i$ 分。

要求让老鼠 $a$ 恰好吃掉 $k$ 块奶酪，使得两只老鼠的总得分最大。

求该最大得分。

题意分析

每块奶酪只能选一次，且必须分配给老鼠 $a$ 或 $b$ 。

由于老鼠 $a$ 必须恰好吃 $k$ 块，我们不能暴力枚举所有 $C(n, k)$ 种组合。我们需要一个高效的贪心策略来判断哪些奶酪更适合给老鼠 $a$ 。

解题思路

差值排序 + 贪心

对于每一块奶酪 $i$ ，我们定义其给老鼠 $a$ 比给老鼠 $b$ 更划算的程度为：

$c_i = a_i - b_i$

然后按 $c_i$ 从大到小排序，表示“更应该被 $a$ 吃”的优先级。

策略如下：

选择前 $k$ 个 $c_i$ 最大的奶酪给老鼠 $a$ 吃；
剩下的 $n - k$ 块给老鼠 $b$ 吃；
这样在满足 $a$ 恰好吃 $k$ 块的条件下，总得分最大。

为什么正确？

这是典型的贪心选择原理。每块奶酪的“增益”就是 $a_i - b_i$ ：

当 $c_i$ 越大，意味着越应该由 $a$ 吃；
选取 $k$ 个最大 $c_i$ 即可。

时间复杂度分析

计算差值 $c_i$ ： $O(n)$ ；
排序 $c_i$ ： $O(n \log n)$ ；
累加前 $k$ 个 $a_i$ ，后 $n - k$ 个 $b_i$ ： $O(n)$ ；

总时间复杂度为： $\boxed{O(n \log n)}$

在 $n \le 1000$ 的范围内完全可接受。

代码演示

#include <iostream>
#include <algorithm>
using namespace std;

struct Cheese {
    int a, b, c; // a 分，b 分，a-b
} cheese[1010];

bool cmp(Cheese x, Cheese y) {
    return x.c > y.c; // 按照 a-b 从大到小排序
}

int main() {
    int n, k;
    cin >> n >> k;

    // 输入 a 数组
    for (int i = 1; i <= n; i++)
        cin >> cheese[i].a;

    // 输入 b 数组并计算差值
    for (int i = 1; i <= n; i++) {
        cin >> cheese[i].b;
        cheese[i].c = cheese[i].a - cheese[i].b;
    }

    // 按照差值排序
    sort(cheese + 1, cheese + n + 1, cmp);

    // 前 k 块给 a 吃，后面的给 b 吃
    int sum = 0;
    for (int i = 1; i <= k; i++) sum += cheese[i].a;
    for (int i = k + 1; i <= n; i++) sum += cheese[i].b;

    cout << sum << endl;
    return 0;
}。

A605. 入栈出栈

题目大意

给定一个长度为 $n$ 的整数序列，表示这 $n$ 个数按照给定顺序依次入栈（即先后调用 $push$ 操作），求它们全部入栈后再逐个出栈时的出栈序列。

题意分析

由于栈是**后进先出（LIFO）**的数据结构：

第一个入栈的元素会最后出栈；
最后一个入栈的元素会最先出栈。

因此，本题本质就是：将输入序列反过来输出即可。

解题思路

将所有输入的整数按顺序压入栈；
然后从栈中依次弹出元素并输出，即为出栈序列。

时间复杂度分析

入栈操作： $O(n)$ ；
出栈操作： $O(n)$ ；
总时间复杂度： $\boxed{O(n)}$ ；
空间复杂度为 $O(n)$ （栈的大小）。

由于 $n < 100$ ，该方法在时空范围内完全安全。

代码演示

#include <bits/stdc++.h>
using namespace std;

int main() {
    stack<int> st;
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        st.push(x); // 入栈
    }

    while (!st.empty()) {
        cout << st.top() << " "; // 输出栈顶
        st.pop(); // 弹出栈顶
    }
    return 0;
}

T46399.模拟栈操作

题目大意

模拟一个栈的数据结构，支持以下 $5$ 种操作：

push x：将整数 $x$ 压入栈；
pop：弹出栈顶元素，若成功输出 pop x，否则输出 pop fail；
top：查看栈顶元素，若成功输出 top = x，否则输出 top fail；
size：输出当前栈内元素个数 size = x；
empty：判断栈是否为空，输出 yes 或 no。

题意分析

本题是典型的栈的模拟题，难度不高，只要正确维护栈的操作和边界判断即可。

由于操作数量较小（ $n \le 100$ ），不涉及任何性能优化问题，直接用标准库的 stack<int> 即可完成。

解题思路

使用 stack<int> 存储数据；
遍历每一条命令，根据命令类型执行对应逻辑；
对于 pop 和 top 操作需要额外判断栈是否为空，以避免访问空栈；
其余操作直接输出对应信息即可。

时间复杂度分析

每次操作均为 $O(1)$ ；
总体时间复杂度为 $O(n)$ ，其中 $n$ 为操作数量。

代码演示

#include <bits/stdc++.h>
using namespace std;

int main() {
    stack<int> st;
    int n;
    cin >> n;
    while (n--) {
        string op;
        cin >> op;

        if (op == "push") {
            int x;
            cin >> x;
            st.push(x);
        } 
        else if (op == "pop") {
            if (st.empty()) 
                cout << "pop fail\n";
            else {
                cout << "pop " << st.top() << '\n';
                st.pop();
            }
        } 
        else if (op == "top") {
            if (st.empty()) 
                cout << "top fail\n";
            else 
                cout << "top = " << st.top() << '\n';
        } 
        else if (op == "size") {
            cout << "size = " << st.size() << '\n';
        } 
        else if (op == "empty") {
            cout << (st.empty() ? "yes" : "no") << '\n';
        }
    }
    return 0;
}

T46400.表达式括号匹配

题目大意

给定一个以 @ 结尾的数学表达式（长度不超过 $255$ ），表达式由小写字母、运算符 + - * /、左右圆括号 ( 和 ) 组成。

要求判断该表达式中的圆括号是否匹配，即每一个左括号 ( 都有对应的右括号 ) 与之匹配，且顺序合理。

如果匹配，输出 YES；否则输出 NO。

题意分析

本题是经典的括号匹配问题，可使用栈来实现匹配判定：

每遇到一个 (，将其压入栈；
每遇到一个 )，尝试从栈中弹出一个 (，若栈为空则说明不匹配；
最后若栈非空，说明还有未匹配的 (，也不合法。

解题思路

遍历整个表达式，忽略所有非括号字符；
用一个栈存储每一个左括号 (；
遇到 ( 就入栈；
遇到 )：
- 若栈非空，则弹出一个；
- 若栈为空，则立即判断不合法；
表达式读完后，如果栈为空，则合法（匹配成功）。

时间复杂度分析

每个字符最多被处理一次；
栈操作为 $O(1)$ ；

总时间复杂度为： $\boxed{O(n)}$

其中 $n$ 为表达式长度，最大不超过 $255$ 。

代码演示

#include <iostream>
#include <stack>
using namespace std;

int main() {
    char ch;
    stack<char> s;
    bool valid = true;

    while (cin >> ch && ch != '@') {
        if (ch == '(') {
            s.push(ch);
        } else if (ch == ')') {
            if (!s.empty()) {
                s.pop();
            } else {
                valid = false; // 无匹配的左括号
            }
        }
    }

    // 如果还有未配对的左括号，也不合法
    if (!s.empty()) valid = false;

    cout << (valid ? "YES" : "NO") << endl;
    return 0;
}

A670. 模拟队列操作

题目大意

给定一系列队列操作，格式如下：

1 x：将元素 $x$ 入队；
2：将队首元素出队；
3：访问队首元素，输出其值；

当遇到非法操作（即操作时队列为空）时，输出 "impossible!"。

题意分析

本题是一个标准的队列模拟题，只需要按照题意依次执行操作：

入队使用 q.push(x)；
出队使用 q.pop()，前提是 q 不为空；
查看队首使用 q.front()，也要求队列非空。

解题思路

使用 queue<int> 来模拟队列结构；
遍历 $n$ 次，每次读取一条指令；
对于每条指令判断是否合法（是否对空队列进行非法操作）；
合法则执行操作并按格式输出；
不合法则输出 "impossible!"。

时间复杂度分析

每条操作均为 $O(1)$ ；
总时间复杂度为 $O(n)$ ，其中 $n$ 为操作次数；

空间复杂度为 $O(n)$ （最坏情况下队列长度为 $n$ ）。

代码演示

#include <bits/stdc++.h>
using namespace std;

int main() {
    queue<int> q;
    int n;
    cin >> n;
    while (n--) {
        int op;
        cin >> op;
        if (op == 1) {
            int x;
            cin >> x;
            q.push(x);
        }
        else if (op == 2) {
            if (q.empty()) cout << "impossible!" << '\n';
            else q.pop();
        }
        else if (op == 3) {
            if (q.empty()) cout << "impossible!" << '\n';
            else cout << q.front() << '\n';
        }
    }
    return 0;
}

A29683. 发牌游戏【队列】

题目大意

小龟用 $k$ 张编号为 $1$ 到 $k$ 的纸牌和 $n-1$ 个朋友一起玩牌，总共 $n$ 个玩家。

游戏规则如下：

最开始将牌堆顶的牌（最前面的牌）发给第 $1$ 个玩家（小龟右手边）；
发完一张牌后，从牌堆顶将接下来的 $p$ 张牌依次移到底部；
然后继续将下一张牌发给下一个人，按逆时针方向，循环进行；
按上述顺序，依次输出所有发出去的纸牌编号。

输入为整数 $k$ 、 $n$ 、 $p$ ，请输出每张牌被发出的顺序编号。

题意分析

这实际上是一个队列循环模拟问题：

牌堆为一个队列，模拟牌的进出；
每次操作都遵循「发牌 + 移动 $p$ 张牌到底部」的规则；
按照玩家的顺序发牌，每次更新发牌人指针（不影响实际模拟逻辑，只需顺序正确）；
直到所有 $k$ 张牌发完，输出其发牌顺序。

解题思路

初始化队列，将牌编号 $1$ 到 $k$ 依次入队；
用一个循环模拟发牌过程：
- 每次将队首元素弹出并输出；
- 然后将接下来的 $p$ 张牌移到队列末尾（每张都是：取出队首 → 再压入队尾）；
循环直到队列为空，即 $k$ 张牌全部发出。

注意： 不需要真的模拟发给哪个人，只要按顺序处理即可。

时间复杂度分析

每次操作：

发一张牌： $O(1)$ ；
移动 $p$ 张牌： $O(p)$ ；

总共 $k$ 张牌，最多执行 $k$ 次发牌，每次最多执行 $p$ 次额外操作：

$\text{总复杂度} = O(k \cdot p)$

题目范围为 $k, n, p < 10000$ ，在 $O(10^8)$ 级别以下，仍可接受。

代码演示

#include <iostream>
#include <queue>
using namespace std;

int main() {
    queue<int> q;
    int k, n, p;
    cin >> k >> n >> p;

    // 初始化牌堆
    for (int i = 1; i <= k; i++) {
        q.push(i);
    }

    // 模拟发牌过程
    while (!q.empty()) {
        // 发出一张牌
        cout << q.front();
        q.pop();

        if (!q.empty()) cout << " ";
        else cout << '\n';

        // 移动 p 张牌到底部
        for (int i = 0; i < p && !q.empty(); i++) {
            q.push(q.front());
            q.pop();
        }
    }

    return 0;
}

有帮助，赞一个

去预览

0/2000

这里空空如也

T46773.【贪心算法(二)】跳跃游戏

题目大意

题意分析

解题思路

时间复杂度解析

代码演示

T46772.【贪心算法(二)】柠檬水找零

题目大意

题意分析

解题思路

时间复杂度解析

代码演示

T46771.【贪心算法(二)】纪念品分组

题目大意

题意分析

解题思路

时间复杂度解析

代码演示

T48915.【贪心算法(二)】老鼠吃奶酪

题目大意

题意分析

解题思路

差值排序 + 贪心

为什么正确？

时间复杂度分析

代码演示

A605. 入栈出栈

题目大意

题意分析

解题思路

时间复杂度分析

代码演示

T46399.模拟栈操作

题目大意

题意分析

解题思路

时间复杂度分析

代码演示

T46400.表达式括号匹配

题目大意

题意分析

解题思路

时间复杂度分析

代码演示

A670. 模拟队列操作

题目大意

题意分析

解题思路

时间复杂度分析

代码演示

A29683. 发牌游戏【队列】

题目大意

题意分析

解题思路

时间复杂度分析

代码演示

热门讨论