本文共 1763 字，大约阅读时间需要 5 分钟。

题目链接

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

思路

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

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

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

在这个序列中，无论先合并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/