AcWing 2725. 数字序列 题解

题目分析

本题给定一个整数序列(a_1, a_2, \cdots, a_n)，要求找出一个递增序列(b_1 < b_2 < \cdots < b_n)，使得(\vert a_1 - b_1\vert + \vert a_2 - b_2\vert + \cdots + \vert a_n - b_n\vert)的值最小。

解题思路

本题的核心思路是利用左偏树来维护一些区间的信息，通过对原序列进行一定的变换，使得问题能够转化为左偏树的相关操作。
1. 对原序列(a_i)进行变换，令(v[i] = a[i] - i)，这样做的目的是将寻找递增序列(b_i)的问题转化为在新序列上的操作，方便后续利用左偏树求解。
2. 利用左偏树来合并一些区间，在合并过程中根据区间大小的奇偶性进行调整，以保证最终得到的结果满足题目要求。
3. 最后根据得到的结果计算绝对值之和的最小值，并还原出序列(b_i)。

代码逐段分析

1. 头文件和全局变量定义

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;
const int N = 1000010;

int n;
int v[N], dist[N], l[N], r[N];
struct Segment
{
    int end, root, size;
}stk[N];
int ans[N];

• 引入必要的头文件，iostream用于输入输出，cstring用于字符串操作，algorithm用于算法相关功能。
• 定义LL为long long的别名，方便后续使用。
• 定义常量N表示序列的最大长度。
• 变量n表示序列的长度。
• v[N]用于存储变换后的序列值；dist[N]存储左偏树节点的距离；l[N]和r[N]分别存储左偏树节点的左子节点和右子节点编号。
• 定义结构体Segment，其中end表示区间的结束位置，root表示该区间对应的左偏树的根节点，size表示区间的大小。stk[N]用于模拟栈，存储这些区间信息。

• ans[N]用于存储最终得到的序列(b_i)（经过一定处理后的值）。

• 左偏树合并函数

int merge(int x, int y)
{
    if (!x || !y) return x + y;
    if (v[x] < v[y]) swap(x, y);
    r[x] = merge(r[x], y);
    if (dist[r[x]] > dist[l[x]]) swap(r[x], l[x]);
    dist[x] = dist[r[x]] + 1;
    return x;
}

• 该函数用于合并两个左偏树(x)和(y)。
• 如果(x)或(y)为空，直接返回非空的那个树（若都为空则返回(0)）。
• 确保(x)的根节点值大于等于(y)的根节点值，若不满足则交换(x)和(y)。
• 将(y)合并到(x)的右子树中。
• 检查并维护左偏性质，若右子树距离大于左子树距离，则交换左右子树。
• 更新(x)的距离为其右子树距离加(1)。

• 最后返回合并后的左偏树的根节点。

• 左偏树删除根节点函数

int pop(int x)
{
    return merge(l[x], r[x]);
}

该函数用于删除左偏树(x)的根节点，通过合并其左右子树来实现，返回新的左偏树。

1. 主函数

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%d", &v[i]);
        v[i] -= i;
    }

• 读取序列的长度(n)。
• 读取原序列(a_i)，并对每个元素进行变换，令(v[i] = a[i] - i)。

    int tt = 0;
    for (int i = 1; i <= n; i ++ )
    {
        auto cur = Segment({i, i, 1});
        dist[i] = 1;
        while (tt && v[cur.root] < v[stk[tt].root])
        {
            cur.root = merge(cur.root, stk[tt].root);
            if (cur.size % 2 && stk[tt].size % 2)
                cur.root = pop(cur.root);
            cur.size += stk[tt].size;
            tt -- ;
        }
        stk[ ++ tt] = cur;
    }

• 初始化栈顶指针tt = 0。
• 遍历变换后的序列：
  • 对于每个位置(i)，创建一个新的区间结构体cur，表示从位置(i)开始的长度为(1)的区间，其左偏树的根节点为(i)，距离为(1)。
  • 当栈不为空且当前区间的根节点值小于栈顶区间的根节点值时，进行合并操作：
    • 合并当前区间的左偏树和栈顶区间的左偏树。
    • 如果当前区间大小和栈顶区间大小均为奇数，删除合并后左偏树的根节点（调用pop函数）。
    • 更新当前区间的大小，并将栈顶元素出栈。
  • 将当前区间结构体入栈。

    for (int i = 1, j = 1; i <= tt; i ++ )
    {
        while (j <= stk[i].end)
            ans[j ++ ] = v[stk[i].root];
    }

• 遍历栈，将每个区间对应的左偏树的根节点值赋值给ans数组，填充ans数组，得到一个与原序列长度相同的数组。

    LL res = 0;
    for (int i = 1; i <= n; i ++ ) res += abs(v[i] - ans[i]);
    printf("%lld\n", res);
    for (int i = 1; i <= n; i ++ )
        printf("%d ", ans[i] + i);

    return 0;
}

• 计算绝对值之和的最小值：遍历v数组和ans数组，计算(\vert v[i] - ans[i]\vert)的和，存储在res中。
• 输出绝对值之和的最小值res。
• 还原并输出序列(b_i)：由于之前对原序列进行了(v[i] = a[i] - i)的变换，这里将ans[i]加上(i)得到最终的(b_i)并输出。

时间复杂度分析

• 读入数据的时间复杂度为(O(n))，其中(n)是序列的长度。
• 构建左偏树并进行合并操作的过程，每个元素最多进栈和出栈一次，每次合并操作时间复杂度为(O(log n))，总体时间复杂度为(O(n log n))。
• 计算绝对值之和以及输出结果的时间复杂度为(O(n))。
• 因此，总的时间复杂度为(O(n log n))。

空间复杂度分析

主要空间消耗在于存储序列的数组、左偏树的相关数组以及模拟栈的结构体数组，空间复杂度为(O(n))，其中(n)是序列的长度。