E. Arranging The Sheep - 题解

比赛与标签

比赛: Codeforces Round 719 (Div. 3) 标签: greedy, math 难度: *1400

题目大意喵~

主人你好呀~ 这道题是关于一群可爱的小羊（'*'）的喵！(ฅ'ω'ฅ)

我们有一个长度为 n 的字符串，里面有小羊（'*'）和空地（'.'）。我们的任务是移动这些小羊，让它们紧紧地挨在一起，形成一个连续的羊群，就像 ...***... 这样。

每次移动，我们可以把一只小羊向左或向右移动一格，但前提是目标格子必须是空的。目标是用最少的总移动次数，完成羊群的排列。

输入格式:

• 第一行是一个整数 t，表示有 t 组测试数据。
• 每组数据第一行是一个整数 n，表示字符串的长度。
• 第二行是长度为 n 的字符串。

输出格式:

• 对每组数据，输出一个整数，表示排列好羊群所需的最少移动次数。

解题思路喵！

这道题看起来是要我们找一个最佳的“集合点”，让所有小羊都靠过去。但是，它们不是集合到一个点，而是要形成一个连续的队伍。那么这个队伍的最终位置应该在哪里呢？这正是我们要解决的核心问题，喵~

关键的第一步：相对顺序不变！

首先，我们来思考一个非常重要的问题：在移动过程中，两只小羊会互相穿过对方吗？

比如说，最左边的小羊（我们叫它羊A）和它右边的另一只小羊（羊B）。为了总步数最少，羊A会跑到羊B的右边去吗？答案是不会的喵！因为如果它们交换了位置，那它们走过的路程肯定比不交换要多。所以，我们可以得出一个超级重要的结论：所有小羊的相对顺序在移动前后是保持不变的！

最开始在最左边的小羊，最终也一定在羊群的最左边；第二只小羊，最终也一定在羊群的第二位，以此类推。

第二步：把问题变个形！

既然相对顺序不变，那问题就变得清晰多啦！

假设我们有 k 只小羊，它们最初的位置（从0开始编号）分别是 p_0, p_1, p_2, ..., p_{k-1}。 我们的目标是把它们移动到某个连续的位置上，比如 x, x+1, x+2, ..., x+k-1。

根据相对顺序不变的原则，第 i 只小羊（初始在 p_i）最终会移动到 x+i 的位置。 那么，第 i 只小羊的移动距离就是 | (x+i) - p_i |。 总的移动次数就是所有小羊移动距离的总和： TotalMoves = |(x+0) - p_0| + |(x+1) - p_1| + ... + |(x+k-1) - p_{k-1}|

这个式子看起来有点复杂，我们来施展一点魔法把它变简单！把 x 和 i 分开： TotalMoves = |x - (p_0 - 0)| + |x - (p_1 - 1)| + ... + |x - (p_{k-1} - (k-1))|

如果我们令 q_i = p_i - i，那么式子就变成了： TotalMoves = |x - q_0| + |x - q_1| + ... + |x - q_{k-1}|

哇！看呐！现在问题就变成了：在数轴上找到一个点 x，使得它到 q_0, q_1, ..., q_{k-1} 这些点的距离之和最小。

这是一个非常经典的数学问题哦！它的答案是：点 x 应该选择 q 数组的中位数！

最后一步：计算总距离

当中位数确定后，我们只需要计算所有 q_i 到这个中位数的距离总和就好了。

这里有一个非常巧妙的计算方法，代码里就是这么做的！

1. 我们先把 q 数组排个序。
2. 然后，我们把最外层的两个数配对 (q_0, q_{k-1})，它们的距离是 q_{k-1} - q_0。这其实就相当于把它们移动到中位数附近所需要的总步数的一部分。
3. 再把次外层的两个数配对 (q_1, q_{k-2})，计算距离...
4. 一直这样配对下去，把所有配对的距离加起来，就是最终的答案啦！

ans = (q_{k-1} - q_0) + (q_{k-2} - q_1) + ...

这个方法非常优雅，它避免了我们去精确计算中位数的值，而是直接通过配对求出了到中位数的距离总和。是不是很神奇呢？喵~

代码实现喵~ ฅ'ω'ฅ

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    // 提高cin/cout的效率，对大量输入输出很有帮助哦！
    ios::sync_with_stdio(false);
    cin.tie(0);

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        string s;
        cin >> s;

        // 用一个vector来记录所有小羊的初始位置
        vector<int> p;
        for (int i = 0; i < n; i++) {
            if (s[i] == '*') {
                p.push_back(i);
            }
        }

        int k = p.size();
        // 如果没有小羊，那当然一步都不用动啦~
        if (k == 0) {
            cout << "0\n";
            continue;
        }

        // 这是解题的关键一步！创建 q 数组，q[i] = p[i] - i
        // p[i] 是第 i 只羊的初始位置
        // 我们希望第 i 只羊最终在 x+i 的位置
        // 移动距离是 |(x+i) - p[i]| = |x - (p[i]-i)|
        vector<int> q(k);
        for (int i = 0; i < k; i++) {
            q[i] = p[i] - i;
        }

        // 把 q 数组排序，这样才能找到中位数（或者说，才能方便地配对）
        sort(q.begin(), q.end());
        
        // ans需要用long long，因为移动次数可能会很大哦！
        long long ans = 0;

        // 这就是那个巧妙的计算方法喵！
        // 把排序后的 q 数组从两端向中间配对，计算它们的差值并累加
        // (q[k-1]-q[0]) + (q[k-2]-q[1]) + ...
        // 这等价于计算所有元素到中位数的距离之和
        for (int i = 0; i < k/2; i++) {
            ans += (long long)(q[k-1-i] - q[i]);
        }
        
        cout << ans << '\n';
    }
    return 0;
}

复杂度分析的说

• 时间复杂度: O(N) 的说。 在每个测试用例中，我们首先遍历一次长度为 N 的字符串来找到所有 k 只羊的位置，这是 O(N) 的。然后，我们对 k 个元素的 q 数组进行排序，需要 O(k log k) 的时间。最后再遍历一次 q 数组，需要 O(k)。因为羊的数量 k 不会超过字符串长度 N，所以总的时间复杂度是 O(N + k log k)，可以近似看作 O(N) 啦。

• 空间复杂度: O(k) 的说。 我们用了一个 vector p 来存储 k 只羊的位置，又用了一个 vector q 来存储 k 个变换后的值。所以空间复杂度是 O(k)。在最坏的情况下，所有格子都是羊，k 等于 N，所以是 O(N)。

知识点与总结喵~

这道题真是太有趣啦，让我们一起总结一下学到了什么吧！

1. 贪心思想与不变量: 解题的第一步就是发现“小羊的相对顺序不变”这个关键性质。在很多问题中，找到一个不变量或者一个最优策略的共同特征，是打破僵局的关键！
2. 问题转化: 我们通过数学变换 q_i = p_i - i，把一个看似复杂的“排列成线”问题，成功转化成了一个经典的“中位数”问题。学会转化问题，是每个算法高手的必备技能哦！
3. 中位数性质: “数轴上一点到其他所有点的绝对距离之和最小，这个点就是中位数”。这个性质非常有用，不仅在这道题，在很多其他统计和优化问题中也会遇到。
4. 优雅的实现: 代码中计算总距离的方法 (q_{k-1} - q_0) + (q_{k-2} - q_1) + ... 非常巧妙，值得学习和记忆。它让我们无需显式找出中位数，就能得到结果。
5. 注意数据范围: 别忘了，当移动步数可能很大时，要使用 long long 来存储结果，不然会因为溢出而得到错误的答案，那就太可惜了喵！

希望这篇题解能帮助到你！继续加油，享受解题的乐趣吧！喵~ (´｡• ᵕ •｡`) ♡