LQ0143 砍竹子【序列处理】

题目来源：蓝桥杯2022初赛 C++ B组J题

题目描述
这天，小明在砍竹子，他面前有 n 棵竹子排成一排，一开始第 i 棵竹子的高度为 hi.
他觉得一棵一棵砍太慢了，决定使用魔法来砍竹子。
魔法可以对连续的一段相同高度的竹子使用，假设这一段竹子的高度为H，
那么使用一次魔法可以把这一段竹子的高度都变为：

其中 ⌊x⌋ 表示对 x 向下取整。
小明想知道他最少使用多少次魔法可以让所有的竹子的高度都变为1。

输入格式
第一行为一个正整数 n，表示竹子的棵数。
第二行共 n 个空格分开的正整数 hi，表示每棵竹子的高度。
20%的测试数据：n ≤ 1000; hi ≤ 10⁶。
100%的测试数据：n ≤ 2 × 10⁵; hi ≤ 10¹⁸。

输出格式
一个整数表示答案。

输入样例
6
2 1 4 2 6 7

输出样例
5

数据范围与提示
其中一种方案：
2 1 4 2 6 7
→ 2 1 4 2 6 2
→ 2 1 4 2 2 2
→ 2 1 1 2 2 2
→ 1 1 1 2 2 2
→ 1 1 1 1 1 1
共需要 5 步完成。

问题分析
因为hi ≤ 10¹⁸，最多5次魔法计算，加上原数有6个存储单元即可。
也可以用优先队列来实现。
另外一种解法是，使用算法函数max_element()和unique()来实现，但是超时了，规定时间内只通过了30%的测试样例。

AC的C++语言程序如下：

/* LQ0143 砍竹子 */

#include 
#include 
#include 

using namespace std;

typedef long long LL;
const int N = 200000, M = 6;
LL h, t[M], f[N][M];

int main()
{
    memset(f, 0, sizeof f);

    LL ans = 0;
    int n, mcnt = 0;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> h;
        int cnt = 0;
        while (h > 1)
            t[cnt++] = h, h = floor(sqrt(h / 2 + 1));
        mcnt = max(mcnt, cnt);
        ans += cnt;

        for (int j = 0; j < cnt; j++)
            f[i][j] = t[cnt - 1 - j];
    }

    for (int i = 0; i < mcnt; i++)
        for (int j = 1; j < n; j++)
            if (f[j - 1][i] && f[j - 1][i] == f[j][i])
                ans--;

    cout << ans << endl;

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

AC的C++语言程序（优先队列）如下：

/* LQ0143 砍竹子 */

#include 
#include 
#include 

using namespace std;

typedef long long LL;
LL h, last = 0;

int main()
{
    priority_queue<pair<LL, int> > q;

    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> h;
        if (h > 1LL && h != last)
            q.push({h, i});
        last = h;
    }

    int ans = 0;
    while (!q.empty()) {
        pair<LL, int> t = q.top();
        q.pop();

        LL h2 = floor(sqrt(t.first / 2 + 1));
        if (h2 > 1LL)
            q.push({h2, t.second});

        int cnt = 1;
        while (!q.empty()) {
           if (q.top().first == t.first && q.top().second == t.second - cnt++) {
               pair<LL, int> t2 = q.top();
               q.pop();
               if (h2 > 1LL)
                   q.push({h2, t2.second});
           } else
               break;
        }
        ans++;
    }

    cout << ans << endl;

    return 0;
}
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
42
43
44
45
46
47
48
49
50

AC的C++语言程序（算法函数）如下：

/* LQ0143 砍竹子 */

#include 
#include 
#include 

using namespace std;

typedef long long LL;
const int N = 200000;
LL h[N];

int main()
{
    LL last = 0;
    int n, m = 5;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> h[m];
        if (h[m] != last) last = h[m++];
    }

    int cnt = 0;
    while (m > 0) {
        int k = max_element(h, h + m) - h;
        if (h[k] == 1) break;
        cnt++;
        h[k] = floor(sqrt(h[k] / 2 + 1));
        m = unique(h, h + m) - h;
    }

    cout << cnt << endl;

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