AcWing 贪心专题章节笔记

贪心题的关键不在代码，而在于“为什么当前选择不会让未来更差”。
如果这一点说不清，十有八九还不能直接上贪心。

本章核心模板

区间选点 / 最大不相交区间数量

1
2
3
4
5
6
7
8
9
10
11
sort(segs.begin(), segs.end(), [](auto& a, auto& b) {
    return a.second < b.second;
});

int res = 0, ed = -2e9;
for (auto [l, r] : segs) {
    if (l > ed) {
        res++;
        ed = r;
    }
}

区间分组

1
2
3
4
5
6
7
8
9
10
sort(segs.begin(), segs.end());
priority_queue<int, vector<int>, greater<int>> heap;
for (auto [l, r] : segs) {
    if (heap.empty() || heap.top() >= l) heap.push(r);
    else {
        heap.pop();
        heap.push(r);
    }
}
cout << heap.size() << endl;

Huffman / 排序不等式 / 货仓选址

1
2
3
4
5
6
7
8
9
priority_queue<int, vector<int>, greater<int>> heap;
for (int x : a) heap.push(x);
int res = 0;
while (heap.size() > 1) {
    int a = heap.top(); heap.pop();
    int b = heap.top(); heap.pop();
    res += a + b;
    heap.push(a + b);
}

本章题目与题解要点

区间问题

  • 905 区间选点：按右端点排序，优先选结束最早的点。
  • 908 最大不相交区间数量：和区间选点本质一致，也是按右端点排序。
  • 906 区间分组：最少分组数等于同时重叠的最多区间数，用小根堆维护当前组的最小右端点。
  • 907 区间覆盖：每次在所有左端点不超过当前起点的区间里，选右端点最远的那个。

Huffman 树

排序不等式

绝对值不等式

推公式

  • 125 耍杂技的牛：按照 w + s 排序，再维护前缀重量，最小化最大风险值。

这一章怎么复习

  1. 先把 905、906、907 三个区间题放在一起对比。
  2. 再做 148 和 913，体会“局部最优 -> 整体最优”的证明方式。
  3. 最后记住 104 的中位数结论和 125 的排序关键字。

返回导航