AcWing

[寒假每日一题]Day-1《货仓地址》

nkul · 1月26日 · 2021年 76次已读

题目

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

输入格式

第一行输入整数\(N\)。
第二行\(N\)个整数\(A_{1} – A_{N}\)

输出格式

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

数据范围

\(
1 \leq N \leq 100000,
1 \leq A_{i} \leq 4000,
\)

样例

输入样例:
4
6 2 9 1

输出样例:
12

题解

不妨设货仓的位置为\(x\),那么货仓x到商店之和为\(\sum\limits_1^n abs(x-a_{i})\),要求是使其值最小的\(x\)。

结论:将\(n\)个点排序,若\(n\)为奇数,\(x\)为中数;若\(n\)为偶数,则\(x\)为中数之间任何一点!

证明

特殊化,设\( n = 2 \),则当\(x\)处于两点之间时,\(x\)到两点之和距离最小,即\( abs(x-a) + abs(x-b) \geq abs(a-b)\).

一般化,设\( a_{1}…a_{n}\)已有序,将\(a_{1}\)和\(a_{n}\)、\(a_{2}\)和\(a_{n-1}\) … 做成一组!n为奇数多一个数单独成组!对每一组都使用上述绝对值不等式,有

$$\sum\limits_1^n abs(x-a_{i}) \geq (a_{n} – a_{1}) + (a_{n-1} – a_{2}) …. $$

其中等号成立的情况为:\(x\)介于\(a_{1}\)和\(a_{n}\)之间,\(a_{2}\)和\(a_{n-1}\)之间,从而有了上述结论!

代码

#include < iostream >
#include < algorithm >
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;
    // x = n/2,求距离!下式中n/2 也可以改成i/2。
    for(int i = 0; i < n; i++) res += abs(a[i] - a[n/2]);
    cout<< res << endl;
    
    return 0;
}

$$ \sum\limits_1^n abs(a_{i} - a_{ \frac{n}{2}}) \equiv \sum\limits_1^nabs(a_{i} - a_{ \frac{i}{2}})) $$

相关题目

1、一维拓展到二维:https://www.acwing.com/problem/content/3170/

2、* 拓展到d维:模拟退火算法!



0 条回应

必须 注册 为本站用户, 登录 后才可以发表评论!