CF962D Merge Equals

发表于 | 分类于
字数统计 : 434   |   阅读时长 ≈ 2 mins.

题目

链接

CF962D Merge Equals

题意简述

给出一个长度为 $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))$ 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
#define REG register
#define IN inline
#define For(x,y,z) for (REG int (x) = (y); (x) <= (z); ++(x))
#define FOR(x,y,z) for (REG int (x) = (y); (x) <  (z); ++(x))
const int kmax_num = 1e6 + 10, kmax_int = 2147483647, kmod = 1e9+7;

#define pli std::pair<long long, int>
#define mp std::make_pair

int n;
long long f[kmax_num];

std::set<pli> set;

int main() {
    std::cin >> n;
    FOR(i,0,n)	std::cin >> f[i], set.insert(mp(f[i], i));

    REG pli t1, t2;
    while(!set.empty())	{
        t1 = *set.begin(), t2 = *(++set.begin());
        if(t1.first != t2.first)	{
            set.erase(set.begin());
        }
        else	{
            set.insert(mp(t1.first << 1, t2.second));
            f[t1.second] = 0;
            f[t2.second] = t1.first << 1;
            set.erase(set.begin());
            set.erase(set.begin());
        }
    }

    REG int ans = 0;
    FOR(i,0,n)	if(f[i])	++ans;
    printf("%d\n", ans);
    FOR(i,0,n)	if(f[i])	printf("%lld ", f[i]);
    printf("\n");
    return 0;
}

杂项

  • 这里用 $std::set$ 实现，$std::set$ 大法好！
  • 这里还用了 $std::pair$ 实现，$std::pair$ 大法好！
  • 这道题在洛谷上居然是蓝题！！还不去水一发吗2333