题目描述

链接：https://ac.nowcoder.com/acm/contest/1001/B

在一条数轴上有N家商店，它们的坐标分别为 A[1]~A[N]。现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。

输入描述

第一行一个整数N，第二行N个整数A[1]~A[N]。

输出描述:

一个整数，表示距离之和的最小值。

思路

直觉告诉我，选址一定要选在最外侧的两间商店中间，货仓到每家商店的距离之和才有可能最短，就这样写代码会超时，直觉又告诉我，选址一定要选在最内侧距离最外侧某家商店的距离最远的这家商店以及相邻靠近这家最外侧商店的商店的中间。靠的都是直觉。

代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits.h>

class mySolution{
public:
    int minDistance(std::vector<int> shops){
        int minDist=INT_MAX;
        int length=shops.size();
        std::sort(shops.begin(),shops.end());
        int min=shops[0],max=shops[length-1];
        int middle=length/2;
        if((max-shops[middle])>=(shops[middle]-max)){
            min=shops[middle];
            max=shops[middle+1];
        }
        else{
            min=shops[middle-1];
            max=shops[middle];
        }
        for(int location=min;location<=max;location++){
            int distacne=0;
            int left=0,right=length-1;
            while(left<right){
                distacne+=(std::abs(shops[left]-location)+std::abs(shops[right]-location));
                left++;
                right--;
            }
            minDist=std::min(minDist,distacne);
        }
        return minDist;
    }
};

int main(){
    mySolution*solution=new mySolution();
    int n;
    int max=INT_MIN,min=INT_MAX;
    std::cin>>n;
    std::vector<int> shops(n);
    while(n--){
        int a;
        std::cin>>a;
        shops[n]=a;
    }
    int answer=solution->minDistance(shops);
    std::cout<<answer<<std::endl;
    delete solution;
    solution=nullptr;
    
    return 0;
}