AcWing

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

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

题目

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

输入格式

第一行输入整数[latex]N[/latex]。
第二行[latex]N[/latex]个整数[latex]A_{1} – A_{N}[/latex]

输出格式

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

数据范围

[latex]
1 \leq N \leq 100000,
1 \leq A_{i} \leq 4000,
[/latex]

样例

输入样例:
4
6 2 9 1

输出样例:
12

题解

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

结论:将[latex]n[/latex]个点排序,若[latex]n[/latex]为奇数,[latex]x[/latex]为中数;若[latex]n[/latex]为偶数,则[latex]x[/latex]为中数之间任何一点!

证明

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

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

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

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

代码

#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 条回应

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