题目链接

给定一个由0到9以及负数符号组成的数字序列，我们需要将相邻相同的数字合并为一个，并计算合并过程中每一次操作所需的最小总距离。每次操作可以选择合并相邻的两个相同数字，或者选择一个更长的连续相同数字进行合并。我们的目标是找到一种合并顺序，使得总距离最小。

思路

为了找到最优的合并顺序，我们可以采用贪心算法。具体来说，我们从左到右扫描序列，遇到两个或多个相同的数字时立即合并。为了高效地维护和查询数字的出现位置以及连续相同数字的块，我们可以使用树状数组（Fenwick Tree）来记录数字的位置信息。这样可以在每次合并时快速查询并更新相关的位置信息，从而确保算法的高效性。

例如，考虑以下两种情况：

1 2 2 1

在这个序列中，我们首先合并22，然后合并11。这样可以确保每次合并都尽可能地减少后续操作的总距离。

1 2 1 2

在这个序列中，无论先合并11还是22，总距离的结果都是一样的。因此，我们可以随便选择一种合并顺序。

通过这种贪心策略，我们可以在一次从左到右的扫描中找到所有可以合并的相同数字对，并用树状数组维护它们的出现位置，从而高效地计算出最小的总距离。

代码

#include 
   
    #include 
    
     const int maxn = 100000;int read() {    int x = 0, f = 1;    char ch = getchar();    while ((ch < '0') || (ch > '9')) {        if (ch == '-') {            f = -f;        }        ch = getchar();    }    while ((ch >= '0') && (ch <= '9')) {        x = x * 10 + ch - '0';        ch = getchar();    }    return x * f;}namespace tree_array {    int c[maxn + 10];    inline int lowbit(int x) {        return x & (-x);    }    inline int add(int pos, int x) {        while (pos <= n) {            c[pos] += x;            pos += lowbit(pos);        }        return 0;    }    inline int sum(int pos) {        int res = 0;        while (pos > 0) {            res += c[pos];            pos -= lowbit(pos);        }        return res;    }}int main() {    n = read();    for (register int i = 1; i <= n; ++i) {        a = read();        if (!pre[a]) {            pre[a] = i;            tree_array::add(i, 1);        } else {            ans += tree_array::sum(i) - tree_array::sum(pre[a] - 1) - 1;            tree_array::add(pre[a], -1);        }    }    printf("%d\n", ans);    return 0;}

上述代码实现了一个基于贪心算法的解决方案，使用树状数组来高效维护数字的位置信息。通过一次从左到右的扫描，我们可以在每一步找到所有可以合并的相同数字对，并更新相关的位置信息，从而计算出最小的总距离。

转载地址：http://aywo.baihongyu.com/

你可能感兴趣的文章