绝对值不等式（贪心）

文章目录

前言

一、贪心

二、AcWing 104. 货仓选址

本题解析

AC代码

三、时间复杂度

前言

复习acwing算法基础课的内容，本篇为讲解基础算法：贪心——绝对值不等式，关于时间复杂度：目前博主不太会计算，先鸽了，日后一定补上。

一、贪心

贪心：利益最大化，即找到最优的情况，贪心问题难在证明，即你可能能推断出这个题目的正确解法，但是这个解法下为什么就是最优解不好证明。

二、AcWing 104. 货仓选址

本题链接：AcWing 104. 货仓选址

本博客提供本题截图：

本题解析

如果店铺的个数为奇数的时候，那么取最中间的店铺为距离之和最短：即选取(6 / 2)（0 ~ 6为7个店铺为奇数）

如果店铺的个数为偶数的时候，那么如下图所示的区间内的点都可以是我们货仓建立的地点，在这段区间内任何一点都有到所有店铺的距离之和最短：

那么为了我们方便代码的书写，取(7 / 3)的店铺，故综上所述，对于有这么n个排好序的店铺，我们都去(n / 2)号店铺作为货仓的地点即可

AC代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n;
int q[N];
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
    sort(q, q + n);
    int res = 0;
    for (int i = 0; i < n; i ++ ) res += abs(q[i] - q[n / 2]);
    printf("%d\n", res);
    return 0;
}

三、时间复杂度

关于贪心——绝对值不等式的时间复杂度以及证明，后续会给出详细的说明以及证明过程，目前先鸽了。