贪心

数学不等式相关
思路难想，但一般都是考问题转化。证难

区间问题

通用证明思路：
$$ 1.ans>=cnt\\ 2.ans<=cnt\\ 3.从而 ans=cnt $$

区间选点

原题：https://www.acwing.com/problem/content/907/
908.最大不相交区间数量 同理
1. 按右端点给区间升序排序
2. 按顺序枚举区间（有区间含被选过的点则略过，否则选取右端点）
3. 证明：（反证法找矛盾）

参考代码：

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

using namespace std;
const int N = 100005,INF=-1e9-1;//小心边界的设置
int n,ans=0,l,r,bound=INF;

struct st {
    int l, r;
    bool operator<(const st &W)const {
        return r < W.r;
    }
}st[N];

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> st[i].l >> st[i].r;
    }
    sort(st, st + n);

    for(int i=0;i<n;i++)
        if (st[i].l > bound) {
            ans++;
            bound = st[i].r;
        }//记得更新边界

    cout << ans << endl;

    return 0;
}

区间分组

原题：https://www.acwing.com/problem/content/908/
1. 按左端点升序排序
2. 枚举（能否放到组中）

==l[i]>Max_r==
1.存在，放入，更新Max_r
2.不存在，开新组

维护最小值：堆

#include<iostream>
#include<algorithm>
#include<queue>
#include<functional>

using namespace std;
const int N = 100005;
int n;
priority_queue<int, vector<int>, greater<int> >heap;

struct st {
    int l, r;
    bool operator<(const st& W)const {
        return l < W.l;
    }
}st[N];

int main() {
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> st[i].l >> st[i].r;

    sort(st, st + n);
    for (int i = 0; i < n; i++) {
        auto r = st[i];
        if (heap.empty() || heap.top() >= r.l)
            heap.push(r.r);//新建一个区间
        else {
            int t = heap.top();
            heap.pop();
            heap.push(r.r);
        }
    }

    cout << heap.size() << endl;

    return 0;
}

区间覆盖

原题：https://www.acwing.com/problem/content/909/
1. 左端点升序排序
2. 枚举区间，在所有能覆盖start的区间中选择右端点最大的区间，更新start为右端点最大值

#include<iostream>
#include<algorithm>
#include<queue>
#include<functional>

using namespace std;
const int N = 100005;
int n,s,t,ans=0;
bool tag = false;
priority_queue<int, vector<int>, greater<int> >heap;

struct st {
    int l, r;
    bool operator<(const st& W)const {
        return l < W.l;
    }
}st[N];

int main() {
    cin >> s >> t;//左右端点
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> st[i].l >> st[i].r;

    sort(st, st + n);
    for (int i = 0; i < n; i++) {
        int j = i, r = -1e9 - 1;//双指针
        while (j < n && st[j].l <= s) {
            r = max(r, st[j].r);
            j++;//在所有能覆盖s的区间中选择右端点最大的点
        }
        if (r < s) {
            ans = -1;
            break;//找不到这样的点，覆盖不了
        }
        ans++;
        if (r >= t) {
            tag = true;//真正找到了
            break;//在右端点的右边，完全可以覆盖
        }
        s = r;//更新起点start为右端点最大值
        i = j - 1;//直接跳过去

    }
    if (!tag)//还是没找到
        ans = -1;

    cout << ans << endl;

    return 0;
}

Huffman树

有多少个父节点就被合并多少次——>权值大的放前
每次合并最小的两堆
1. 权值最小的两点深度最深，互为兄弟
2. f(n) = f(n-1)+a+b （减而治之，第一步先弄出来）

#include<iostream>
#include<algorithm>
#include<queue>
#include<functional>

using namespace std;
int n,x,ans=0,a,b;
priority_queue<int, vector<int>, greater<int> >heap;

int main() {
    cin >> n;
    while (n--) {
        cin >> x;
        heap.push(x);
    }

    while (heap.size() > 1) {
        a = heap.top();
        heap.pop();
        b = heap.top();
        heap.pop();
        ans += a + b;
        heap.push(a + b);//减而治之
    }

    cout << ans << endl;

    return 0;
}

排序不等式

越往前被等的越久，所以打水时间最长的排后面
——>升序排列
$$ 总时间 = t_1(n-1)+t_2(n-2)+… $$
该题代码难度不高，记得long long就好

绝对值不等式

分组求和
本质：找中位数
$$ f(x) = |x_1-x|+|x_2-x|+…+|x_n-x| $$

#include<iostream>
#include<algorithm>

using namespace std;
const int N = 100005;
long long n,ans = 0;
int a[N];

int main() {
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    sort(a, a + n);
    for (long long i = 0; i < n; i++)
        ans += (long long)abs(a[i]-a[n/2]);

    cout << ans << endl;

    return 0;
}

推公式

eg.https://www.acwing.com/problem/content/127/
最优：wi + si从小到大排序

#include<iostream>
#include<algorithm>

using namespace std;

typedef pair<int, int>PII;
const int N = 50005;
long long n,ans = -2e9,sum=0;
PII cow[N];

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        int w, s;
        cin >> w >> s;
        cow[i] = { w + s,w };
    }
    sort(cow, cow + n);
    for (int i = 0; i < n; i++) {
        int w = cow[i].second, s = cow[i].first - w;
        ans = max(ans, sum - s);
        sum += w;
    }

    cout << ans << endl;

    return 0;
}