信息奥赛题单｜stack

本篇博客还在持续更新润色中～

STL - stack

题单 🧑🏻‍💻

题目来源	题目名称	题目链接	备注	难度
AtCoder - ABC 120C	Unification	链接🔗	栈模拟	🟢

Unification

题目信息 📚

【题目名称】AtCoder ABC 120C - Unification

【题目描述】

There are $N$ cubes stacked vertically on a desk.

You are given a string $S$ of length $N$. The color of the $i$-th cube from the bottom is red if the $i$-th character in $S$ is 0, and blue if that character is 1.

You can perform the following operation any number of times: choose a red cube and a blue cube that are adjacent, and remove them. Here, the cubes that were stacked on the removed cubes will fall down onto the object below them.

Determine the maximum number of cubes that can be removed.

【输入】

Input is given from Standard Input in the following format:

$S$

【输出】

Print the maximum number of cubes that can be removed.

【数据范围】

• $1 \leq N \leq 10^5$
• $|S| = N$
• Each character in $S$ is either 0 or 1.

【输入样例1】

0011

【输出样例1】

4

【输入样例2】

11011010001011

【输出样例2】

12

【输入样例3】

0

【输出样例3】

0

【原题链接】

https://atcoder.jp/contests/abc120/tasks/abc120_c

---

题目解析 🍉

【题目分析】

用「栈」模拟该过程即可。（可以借助 STL 中的 stack ）

【C++ 代码】

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;

int main() {
    string str;
    cin >> str;

    // 利用STL中的栈，模拟该过程
    stack<char> s;
    for (auto t: str) {
        // 栈为空，直接将当前元素进栈
        if (s.empty()) s.push(t);
        else {
            // 栈非空，若栈顶元素和当前元素可以消去，直接弹出栈顶元素
            if (s.top() != t) s.pop();
            else s.push(t);  // 否则当前元素进栈
        }
    }
    // 答案即为总数量-栈内剩下的元素数量
    cout << str.size() - s.size() << endl;

    return 0;
}

---

***

题目信息 📚

【题目名称】 -

【题目描述】

【输入】

【输出】

【输入样例】

【输出样例】

【原题链接】

---

题目解析 🍉

【题目分析】

【C++ 代码】

---