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.

【输入】

The 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】

【输出样例1】

All four cubes can be removed by performing the operation as follows:

Remove the second and third cubes from the bottom. Then, the fourth cube drops onto the first cube.
Remove the first and second cubes from the bottom.

【输入样例2】

11011010001011

【输出样例2】

【输入样例3】

【输出样例3】

【题目来源】

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;
}