排序不等式（贪心）

文章目录

前言

一、贪心

二、AcWing 913. 排队打水

本题分析

AC代码

三、时间复杂度

前言

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

一、贪心

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

二、AcWing 913. 排队打水

本题链接：AcWing 913. 排队打水

本博客给出本题截图

本题分析

这里注意爆int问题，所以我们用long long去表达最后的结果

我们按照时间从小到大排序，时间少的先打水

注意是所有人等待时间之和，那么第一个人i = 0是不需要等待的，每次的等待时间是a[i] * (n - i - 1);

AC代码

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 100010;
int a[N];
typedef long long LL;
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
    sort(a, a + n);
    LL res = 0;
    for (int i = 0; i < n; i ++ ) res += a[i] * (n - i - 1);
    printf("%lld", res);
    return 0;
}

三、时间复杂度

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