链接：https://ac.nowcoder.com/acm/problem/50937
来源：牛客网

题目描述

在一条数轴上有N家商店，它们的坐标分别为 A[1]~A[N]。现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。
链接：https://ac.nowcoder.com/acm/problem/50937
来源：牛客网

备注: 

对于100%的数据:N≤100000N\leq 100000N≤100000, A[i]≤1000000A[i]\leq 1000000A[i]≤1000000
本题可以使用前缀和和差分去解体，但不是单纯的使用前缀和和差分。
在这里面不是区域性的变化，所以第一眼看上去似乎不能使用前缀和和差分。但是可以创建一个map数组来保存保存在某个区间里面需要做什么样的连续变换（在某个区间里面彼此相加或者相见的数是一样的）。
比如：1：map[INT_MIN]--，map[1]+=2
2：map[INT_MIN]--，map[2]+=2
3：map[INT_MIN]--，map[3]+=2
4：map[INT_MIN]--，map[4]+=2
然后进行前缀和的累加，得到的结果就是在相邻区间里面彼此的差值。然后又有最大值或最小值一定在端点的位置（也就是1，2，6，9的位置）。所以计算出每一个端点的值就可以达到最小的总距离。 
#include <iostream>
#include <cstdio>
#include <limits.h>
#include <map>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)

using namespace std;

const int MAXN = 1000002;
long long first_num = 0;
map<long long, long long> m = {};
long long res[MAXN];

int main() {
    IOS;
    int n, k;
    cin>>n;
    for (int i=1;i<=n;i++) {
        cin>>k;
        m[-INT_MAX]--;
        m[k]+=2;
        first_num+=k+(long long)INT_MAX;
    }
    //计算a的前缀和
    map<long long, long long>::iterator it = m.begin();
    int old = it->second;
    for (++it;it!=m.end();it++) {
        it->second = it->second+old;
        old = it->second;
    }
    res[0] = first_num;
    int min = INT_MAX;
    //根据前缀和和first_num的值进行距离总和的计算
    it = m.begin();
    map<long long, long long>::iterator it2 = m.begin();
    it2++;
    int index = 1;
    for (it;it2!=m.end();it++) {
        res[index] = (it2->first-it->first)*(it->second)+res[index-1];
        if (res[index]<min) {
            min = res[index];
        }
        index++;
        it2++;
    }
    cout<<min;
    return 0;
}