贪心算法的难点：贪心的证明

区间问题

例：最大不相交区间问题：给定一组区间，选择尽可能多的不相交区间。

已知通过贪心算法得到的区间数量为cnt，最大区间数量为ans，因此ans >= cnt；又因为不使用贪心算法的话，每选择一个区间后，为后续区间留下的长度l1较贪心算法相应步骤时留下的长度l2更短，因此ans <= cnt，故证明ans == cnt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// 定义区间结构体
struct Interval {
    int start, end;
};

// 比较函数，按右端点升序排序
bool compareIntervals(const Interval& a, const Interval& b) {
    return a.end < b.end;
}

// 最少区间选点算法
vector<int> minPoints(vector<Interval>& intervals) {
    if (intervals.empty()) return {};

    // 按右端点排序
    sort(intervals.begin(), intervals.end(), compareIntervals);

    vector<int> points; // 存储选中的点
    int lastPoint = intervals[0].end; // 第一个区间的右端点
    points.push_back(lastPoint);

    // 遍历区间
    for (const auto& interval : intervals) {
        // 如果当前区间不包含上一个选中的点
        if (interval.start > lastPoint) {
            lastPoint = interval.end; // 选择当前区间的右端点
            points.push_back(lastPoint);
        }
    }

    return points;
}

哈夫曼树

哈夫曼树是一种带权路径长度最短的二叉树，也称为最优二叉树，它的性质：

  • 权重最小的两个点，深度一定最深，且可以互为兄弟

构建哈夫曼树的过程：

  1. 将所有字符及其频率作为叶子节点，放入一个最小堆（优先队列）。
  2. 每次从堆中取出两个频率最小的节点，合并成一个新节点，新节点的频率为这两个节点的频率之和。
  3. 将新节点重新插入堆中。
  4. 重复上述过程，直到堆中只剩一个节点，这个节点就是哈夫曼树的根节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
HuffmanNode* buildHuffmanTree(const vector<char>& data, const vector<int>& freq) {
    priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare> minHeap;

    // 将所有字符和频率插入最小堆
    for (size_t i = 0; i < data.size(); ++i) {
        minHeap.push(new HuffmanNode(data[i], freq[i]));
    }

    // 构建哈夫曼树
    while (minHeap.size() > 1) {
        HuffmanNode* left = minHeap.top(); minHeap.pop();
        HuffmanNode* right = minHeap.top(); minHeap.pop();

        // 创建新节点，频率为左右子节点频率之和
        HuffmanNode* newNode = new HuffmanNode('$', left->freq + right->freq);
        newNode->left = left;
        newNode->right = right;

        minHeap.push(newNode);
    }

    return minHeap.top(); // 返回根节点
}

绝对不等式

$$
|a-x| + |b-x| \geq |a-b|
$$
问题描述：在一条数轴上有 n个商店，每个商店的位置为$x_i$，现在需要选择一个位置建立货仓，使得货仓到所有商店的距离之和最小。
​
。现在需要选择一个位置建立货仓，使得货仓到所有商店的距离之和最小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

    // 将商店位置排序
    sort(x.begin(), x.end());

    // 选择中位数作为货仓位置
    int warehouse = x[n / 2];

    // 计算总距离
    long long total_distance = 0;
    for (int i = 0; i < n; i++) {
        total_distance += abs(x[i] - warehouse);
    }

    cout << total_distance << endl;
    return 0;
}

推公式

有 n 头牛叠罗汉，每头牛有一个重量$w_i$和一个强壮程度 $s_i$，定义每头牛的风险值为它上方所有牛的重量之和减去它自身的强壮程度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Cow {
    int w, s;
};

bool compare(const Cow& a, const Cow& b) {
    return (a.w + a.s) < (b.w + b.s);
}

int main() {
    int n;
    cin >> n;
    vector<Cow> cows(n);
    for (int i = 0; i < n; i++) {
        cin >> cows[i].w >> cows[i].s;
    }

    // 按照 w + s 从小到大排序
    sort(cows.begin(), cows.end(), compare);

    // 计算最大风险值
    long long total_weight = 0;
    long long max_risk = -1e18;
    for (int i = 0; i < n; i++) {
        max_risk = max(max_risk, total_weight - cows[i].s);
        total_weight += cows[i].w;
    }

    cout << max_risk << endl;
    return 0;
}