题目
链接
题意简述
给出一个长度为 $n (2<= n <= 150000)$ 的数组， 数组内元素 $a{i} (1 <= a{i} <= 1e9)$ 。
每次操作将数组内两个相同的最小的最靠左的元素取出，并将左边的合并到右边，直到不能操作为止，输出最后的数组。
例：
$[1, 1, 3, 1, 1]~rightarrow~[2, 3, 1, 1]~rightarrow~[2, 3, 2]~rightarrow~[3, 4]$
思路
暴力
首先考虑暴力，也就是暴力查找。
时间复杂度： $O(n^{2})$ 。
正解
正解应该挺容易想到的，用堆维护数值和位置，每次取出两个，不相同就删了第一个，否则合并。
时间复杂度： $O(n log(n))$ 。
代码
杂项
- 这里用 $std::set$ 实现，$std::set$ 大法好！
- 这里还用了 $std::pair$ 实现，$std::pair$ 大法好！
- 这道题在洛谷上居然是蓝题！！还不去水一发吗2333