【Codeforces Round #771 (Div. 2)】 1638C. Inversion Graph 题解

写在前面：
特别感谢 pzr 给出的解题思路！
pzr的知乎专栏：https://zhuanlan.zhihu.com/p/467500163

一、题目描述

（一）、原题链接

原题链接：https://codeforces.com/contest/1638/problem/C

（二）、题目大意

有多组测试数据，每组测试数据为长度为n的数组（数组中的数为1~n的乱序排列）。

有如下规则：如果后面的数小于前面的数，就将这两个数（包括这两个数所在的连通块）连起来为一个连通块。

问：给定的数组中连通块的数量是多少？

二、解题思路

那么就以样例中的数据为例分析。

可以发现后一个连通块中的所有数大于前一个连通块中的所有数。并且判断一个数属于不属于一个连通块，只和这个数和连通块的最大值有关。

以连通块（也就是集合）的角度来思考，如果一个数小于前面连通块的最大数，则将这个数添加至连通块中，否则，这个数作为新的连通块。

可得出规律，连通块的最大值是升序排列的。所以考虑单调栈（单调栈即满足单调性的栈结构）的数据结构来存储连通块的最大值，那么最后栈中元素的数量就是连通块的数量。

对于本组测试数据，单调栈中的数据变化为：
【3】->【3】->【3】->【3，6】->【3，6】->【3，6】

不过需要注意的是，当一个数属于当前连通块时，还应该判断是否属于前面的连通块，如果属于，那么将两个连通块合并，新连通块的最大值为两个旧连通块的最大值中更大的那一个。

例如样例中的这组数据。第四个元素为 “2” ，属于以 “5” 为最大值的连通块，同时也属于以 “3” 为最大值的连通块。那么，就将两个连通块合并，新连通块的最大值为 “5” 。

对于本组测试数据，单调栈中的数据变化为：
【3】->【3】->【3，5】->【5】->【5】->【5】

三、注意事项

（一）、思路注意

当一个数属于当前连通块时，还应该继续判断是否属于前面的连通块。

（二）、编码注意

应该注意对栈为空的情况的判断和处理！
其它也基本没啥需要注意的了。

四、代码全览

下面是带有较详细注释的AC代码。

// Inversion Graph
#include <iostream>
#include <stack>
#define DEBUG
using namespace std;void solve(void);int main(void)
{int test;cin >> test;while (test--)solve();return 0;
}// 针对每组数据的解答
void solve(void)
{int n, t;   // 数组元素个数 | 读取数组的临时变量stack<int> stk;     // 存放连通块(实际为连通块中最大值)的栈cin >> n;for (int i = 0; i < n; i++){cin >> t;// 如果栈空，直接入栈if (stk.empty()){stk.push(t);continue;}// 如果这个数大于栈顶，则将这个数入栈// 否则保存栈顶，将栈中大于这个数的元素出栈，然后将原栈顶重新入栈if (t > stk.top())stk.push(t);else{int tt = stk.top();while (!stk.empty() && stk.top() > t)stk.pop();stk.push(tt);}}// 最后，栈中的元素数量就是连通块的数量cout << stk.size() << endl;
}