C++ 算法：奶牛捣乱干草堆，如何快速整理？

农夫约翰精心整理的 N 堆干草，每堆干草的高度相同。

但是，奶牛们趁着他不注意在干草堆之间移动了一些干草捆，使得各个干草堆的高度可能不再相同了。

现在，约翰想要重新整理这 N 堆干草，使得它们的高度都相同。他可以在任意两堆干草之间移动干草捆，每次移动一捆干草捆的时间为 1。请你帮助约翰计算最少需要多少时间才能完成整理。

输入格式:

第一行包含一个整数 N，表示干草堆的数量。

接下来 N 行，每行包含一个整数 H_i，表示第 i 堆干草的高度。

输出格式:

输出一个整数，表示完成整理所需的最少时间。

数据范围:

1≤N≤10^5, 1≤H_i≤10^9

样例输入:

样例输出:

算法 1

(暴力枚举) $O(n^2)$

时间复杂度

$O(n^2)$: 暴力枚举所有可能的平均高度，对于每种平均高度，计算需要移动多少干草捆。

参考文献

C++ 代码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> h(n);
    for (int i = 0; i < n; i++) {
        cin >> h[i];
    }

    int min_time = INT_MAX;
    for (int avg = 1; avg <= 1000000000; avg++) { // 枚举所有可能的平均高度
        int time = 0;
        for (int i = 0; i < n; i++) {
            time += abs(h[i] - avg); // 计算移动干草捆的数量
        }
        min_time = min(min_time, time); // 更新最小时间
    }

    cout << min_time << endl;
    return 0;
}

算法 2

(贪心算法) $O(n)$

时间复杂度

$O(n)$: 只需要遍历一次所有干草堆，计算总高度和平均高度，然后计算移动干草捆的数量。

参考文献

C++ 代码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> h(n);
    long long sum = 0; // 使用 long long 存储总高度，防止溢出
    for (int i = 0; i < n; i++) {
        cin >> h[i];
        sum += h[i];
    }

    int avg = sum / n; // 计算平均高度
    int time = 0;
    for (int i = 0; i < n; i++) {
        time += abs(h[i] - avg); // 计算移动干草捆的数量
    }

    cout << time << endl;
    return 0;
}

解释：

贪心算法的思路是，对于每个干草堆，将其高度调整到平均高度，这样需要移动的干草捆数量是最少的。

注意：

在 C++ 代码中，使用 long long 类型存储总高度，以防止溢出。
可以根据需要选择合适的算法，对于较小的数据范围，暴力枚举算法也足够快，但对于较大的数据范围，贪心算法效率更高。