【acwing 寒假每日一题】day1货仓选址

题目来源 https://www.acwing.com/problem/content/description/106/

题目描述

在一条数轴上有 N 家商店，它们的坐标分别为 A1~AN。

现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。

为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。

输入格式
第一行输入整数N。

第二行N个整数A1~AN。

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

数据范围
1≤N≤100000,
0≤Ai≤40000
输入样例：
4
6 2 9 1
输出样例：
12

思路

这一题的一个经典结论：
对所有点排序 ：
奇数点的话 就是最中间的位置
偶数点的话就是中间两个点之间的任意位置都行

证明：就是基于绝对值不等式，
∣x−a∣+∣x−b∣≥∣a−b∣
我们首先看最简单的情况，数轴上一个点x到a、b（a<b）两个点的距离，我们直观上看到显然x在a、b之间的话会使得x到a的距离+x到b的距离最小，就是abs(b-a)，无论是在a的左边还是b的右边都会比这个值大
那么推广为n个点，我们先对n个点排序，从小到大计为a0-an-1，
1、n是奇数的时候，中点就是n/2和n/2+1,我们将所有点两两分组(a0,an-1),(a1,an-1)…(n/2,n/2+1) 对于每一组都用我们这个结论，得到x在(a0,an-1)之间，在(a1,an-1)之间…在(n/2,n/2+1)之间
2、n是偶数的时候，中点就是n/2,我们将所有点两两分组(a0,an-1),(a1,an-1)…(n/2-1,n/2+1) 和n/2 对于每一组都用我们这个结论，得到x在(a0,an-1)之间，在(a1,an-1)之间…在(n/2-1,n/2+1),在n/2

代码

#include<bits/stdc++.h>

using namespace std;

const int N=100010;

int n;
int a[N];

int main()
{
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    sort(a,a+n);
    int res=0;
    for(int i=0;i<n;i++) res+=abs(a[i]-a[n/2]);
    cout<<res<<endl;
    return 0;
}

题目拓展

1. 一维拓展成2维度 https://www.acwing.com/problem/content/description/3170/ 可以使用三分来做
2. 拓展到高维 比如10维 要用模拟退火来做 一般碰不到 竞赛难度了

一些问题

还有一种写法

#include<bits/stdc++.h>

using namespace std;

const int N=100010;

int n;
int a[N];

int main()
{
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    sort(a,a+n);
    int res=0;
    for(int i=0;i<n;i++) res+=a[i]-a[i/2];
    cout<<res<<endl;
    return 0;
}

这里是将 res+=abs(a[i]-a[n/2]) 改成了res+=a[i]-a[i/2] 看起来是写错了 但却是很尴尬 能ac 原因是两个式子得出的展开得到的结果是一致的 所以能ac 同时 不需要取绝对值了 但是这里并什么用 没有价值