一. 不等式贪心

1. 问题模型

n个人排队打水，每个人打水的时间为 t[i], 如何设置打水顺序使得所有人的排队等待时间最短？

2. 贪心思想，打水最慢最墨迹的排最后，不要耽误别人时间

按照打水时间从小到大的顺序打水，总的打水时间最小

3. 代码模板

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

typedef long long LL;

int main()
{
    int n;
    cin >> n;

    vector<int> t = vector<int>(n, 0);
    for(int i = 0; i < n; i++){
        cin >> t[i];
    }

    sort(t.begin(), t.end());

    LL ans = 0;
    for(int i= 0; i < n; i++){
        ans += (t[i] * (n - i - 1));
    }

    cout << ans << endl;

    return 0;
}

二. 绝对值不等式

1. 问题模型

n个村庄位置，如何设置超市位置，可以使得超市到所有村庄的距离最小

2. 贪心思想

坐标按照从小达到位置排序，中间的位置（奇数中间的那个数位置／偶数中间两个数围成的闭区间任意位置）
放置超市位置可以使得总距离最小

3. 代码模板

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main()
{
    int n;
    cin >> n;

    vector<int> a(n, 0);
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }

    sort(a.begin(), a.end());
    int x = a[a.size() / 2];

    long long ans = 0;
    for(int i = 0; i < n; i++){
        ans += abs(x - a[i]);
    }

    cout << ans << endl;
    return 0;
}

三 推公式贪心

1. 问题模型

n个人叠罗汉，每个人有属性重量 w和强壮 s，
定义一个人的危险系数等于所有在这个人上层重量 w 之和减去这个人自身的强壮 s
问如何能够让所有人当中危险系数最大的人危险系数数值最小？

2. 贪心思想

按照所有人的 重量和强壮属性之和w+s排序叠罗汉，可使得危险系数最大值最小

3. 代码模板

#include<iostream>
#include<vector>
#include<algorithm>
#include<climits>

using namespace std;

struct Node{
    int all;
    int w, s;

    bool operator<(const struct Node& b)
    {
        return all < b.all;
    }
};

int main()
{
    int n;
    cin >> n;

    vector<struct Node> zoo(n);

    for(int i = 0; i < n; i++){
        int w, s;
        cin >> w >> s;
        zoo[i] = {w+s, w, s};
    }

    sort(zoo.begin(), zoo.end());

    int ans = INT_MIN;
    long long prev = 0;
    for(int i = 0; i < n; i++){
        int tmp = prev - zoo[i].s;
        ans = max(ans, tmp);
        prev += zoo[i].w;
    }

    cout << ans << endl;
    return 0;
}