题目链接

算法竞赛进阶指南-18.货仓选址

Method : 排序

思路很明确的一道题，就是要排序后依次计算a[]首尾的元素之间的距离。

使用i < n/2就不需要分奇偶讨论了

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

using namespace std;

typedef long long LL;

int n;
vector<int> a;

int main() {
    cin >> n;
    a.resize(n);
    for (int i = 0; i < n; i ++) {
        scanf("%d", &a[i]);
    }

    sort(a.begin(), a.end());

    LL res = 0;
    for (int i = 0; i < n / 2; i ++)  {
        res += (a[n - i - 1] - a[i]);
    }

    cout << res << endl;

    return 0;
}

复杂度分析

• 时间复杂度${O(nlog_2n)}$， 使用<algorithm>中的sort排序和快排的时间复杂度是相同的 。

• 空间复杂度${O(n)}$，数组a的长度为n。