6.2 贪心算法 | 排序不等式、绝对值不等式、推公式6.2 贪心算法 | 排序不等式、绝对值不等式、推公式

184 阅读 0 评论 122 点赞

我是靠谱客的博主优雅彩虹，这篇文章主要介绍6.2 贪心算法 | 排序不等式、绝对值不等式、推公式6.2 贪心算法 | 排序不等式、绝对值不等式、推公式，现在分享给大家，希望可以做个参考。

6.2 贪心算法 | 排序不等式、绝对值不等式、推公式

这是我的一个算法网课学习记录，道阻且长，好好努力

排序不等式

排队打水

例题： AcWing 913.排队打水

题目描述：

有 n 个人排队到 1 个水龙头处打水，第 i 个人装满水桶所需的时间是 ti，请问如何安排他们的打水顺序才能使所有人的等待时间之和最小？

输入格式

第一行包含整数 n。第二行包含 n 个整数，其中第 i 个整数表示第 i 个人装满水桶所花费的时间 ti。

输出格式

输出一个整数，表示最小的等待时间之和。

数据范围

1≤ n ≤10⁵,
1≤ t_i ≤10⁴

输入样例：

7
3 6 1 4 2 5 7

输出样例：

贪心思路：

按照从小到大的顺序排队，即有排队总时间最小。

证明思路：

调整法。

假设最优解并不是从小到大排序的，必然存在相邻两个数有ti > ti+1 ，容易知道对于其他两个人时间是没有变化的。

考虑第i和第i+1个同学的时间。

调整前：ti * (n-i) + ti+1 * (n-i-1) 调整后：ti+1 * (n-i) + ti * (n-i-1) 两者相减可得ti - ti+1 > 0，可以得到调整后是更小的总时间。经过多次调整后，可以获得从小到大排序的解，也就是最优解。

Ans

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 100010;

int n; // 打水人数
int t[N]; // 每个人所需打水时间

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &t[i]);

    sort(t, t + n); // 从小到大排序

    LL res = 0;
    for (int i = 0; i < n; i ++ ) res += t[i] * (n - i - 1); // 累加

    printf("%lldn", res);

    return 0;
}

绝对值不等式

货仓选址

例题： AcWing 913.排队打水

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

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

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

输入格式：

第一行输入整数 N。

第二行 N个整数 A1∼AN。

输出格式：

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

数据范围

1≤N≤100000,
0≤Ai≤40000

输入样例：

4
6 2 9 1

输出样例：

在这里插入图片描述

贪心思路：

（思路其实包含证明了。）

核心是中位数。

在一个数轴上|a-x|+|b-x|>=|a-b|
当x在a，b正中间，取等号，即a，b到x距离之和最小

这个题是求多个点到一个点距离之和的最小值
可以俩俩配对，即a0与an-1配对，a2与an-2配对，以此类推

x为n个数的中位数的时候距离和取最小

考虑最后中间单个还是双个，即n奇偶问题
当n为奇数时，最后只剩下一个，中位数取这个数就ok，如果n为偶数个，中位数位于两个数之间。

Ans

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
int a[N];

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);

    sort(a, a + n);

    int res = 0;
    for (int i = 0; i < n; i ++ ) res += abs(a[i] - a[n / 2]);

    printf("%dn", res);

    return 0;
}

推公式

很多贪心问题都是先把公式推出来，然后从公式的角度运用不等式的原理，可以得到我们最终的题解。

可以有意识的去看一些数学的证明。

耍杂技的牛

例题： AcWing 125.耍杂技的牛

农民约翰的 N 头奶牛（编号为 1...N）计划逃跑并加入马戏团，为此它们决定练习表演杂技。

奶牛们不是非常有创意，只提出了一个杂技表演：叠罗汉，表演时，奶牛们站在彼此的身上，形成一个高高的垂直堆叠。

奶牛们正在试图找到自己在这个堆叠中应该所处的位置顺序。这 N 头奶牛中的每一头都有着自己的重量 Wi 以及自己的强壮程度 Si。

一头牛支撑不住的可能性取决于它头上所有牛的总重量（不包括它自己）减去它的身体强壮程度的值，现在称该数值为风险值，风险值越大，这只牛撑不住的可能性越高。

您的任务是确定奶牛的排序，使得所有奶牛的风险值中的最大值尽可能的小。

输入样例：

输出样例：

贪心思路：

按照wi + si从小到大的顺序排，最大的危险系数一定是最小的。

证明思路：

已知，对于 $Z^+$ ，有 $w_i>0,s_i>0$ 。

考虑排序前和排序后的情况，对于第i头牛与第i+1头牛（其他牛的情况是不会发生改变的）

	第`i`头牛的危险系数	第`i+1`头牛的危险系数
交换前	$sum_{j=1}^{i-1}w_j-s_i$	$sum_{j=1}^{i-1}w_j+w_i-s_{i+1}$
交换后	$sum_{j=1}^{i-1}w_j+w_{i+1}-s_{i}$	$sum_{j=1}^{i-1}w_j-s_{i+1}$

观察可以发现所有的式子都共有一个部分 $sum_{j= 1}^{i-1}w_j$ ，对其进行简化

	第`i`头牛的危险系数	第`i+1`头牛的危险系数
交换前	$s_i$	$w_i-s_{i+1}$
交换后	$w_{i+1}-s_{i}$	$s_{i+1}$

对于每头牛交换前后情况进行对比

对于第i头牛， $s_i < w_{i+1} - s_i iff 0 < w_{i + 1}$ ，交换后的危险系数更大。

对于第i+1头牛， $s_{i+1} < w_{i} - s_{i+1} iff 0 < w_{i}$ ，交换前的危险系数更大。

题目要求的是最大值当中风险系数最小，可以知道有两种情况，最大危险系数应关注 $w_i-s_{i+1}$ 和 $w_{i+1}-s_{i}$

分类讨论之：

当 $w_i-s_{i+1} ge w_{i+1}-s_{i}$ 时，即 $w_i+s_i ge w_{i+1}+s_{i+1}$ 时，交换后最大危险系数的最小值更小，为更优解。

当 $w_i-s_{i+1} lt w_{i+1}-s_{i}$ 时，即 $w_i+s_i lt w_{i+1}+s_{i+1}$ 时，交换前最大危险系数的最小值更小，为更优解。

因此在算法中对于每头牛所对应的 $s_i+w_i$ 进行排序，然后按照题意进行计算，最终就可以得到最优解。

Ans

#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 50010;

int n;
PII cow[N];

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )
    {
        int w, s;
        scanf("%d%d", &w, &s);
        cow[i] = {w + s, w};
    }

    sort(cow, cow + n);

    int res = -2e9, sum = 0;
    for (int i = 0; i < n; i ++ )
    {
        int w = cow[i].second, s = cow[i].first - w;
        res = max(res, sum - s);
        sum += w;
    }

    printf("%dn", res);
    return 0;
}