算法笔记 - t0x01 贪心
|
阅读次
|
1.6k 字
|
5 分钟

0x0110 贪心思想

我觉得，我把草纸上的东西重新打一遍是一个很傻逼的事情。

0x0111 引入

生活中，用到贪心的地方有很多。举一个例子：买菜的时候，我们一般会“货比三家”，选择性价比最高的。如果还没买够，这家店就卖光了（虽然这种情况一般不会发生），那么就去买性价比次高的，以此类推。抽象成代码即为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void buy(int need, int money)
{
  sort(stores, [](const Store &a, const Store &b)
               { return 1.0 * a.quality / a.cost > 1.0 * b.quality / b.cost; });
  for (auto s : stores)
  {
    int bought = min({s.count, money / s.cost, need});
    s.buy(bought);
    money -= bought * s.cost;
    need -= bought;
    if (need <= 0)
      break;
  }
  return;
}

此例中，我们使用了“取最大值”的贪心思想。

0x0112 常见思想

  • 取最大/优值
    如上。利用一些 DS 维护当前最大值，并每次取最大值。
  • 取最远/近点
    包括一些区间贪心和一些计算几何题，比如最小区间覆盖。此类题一般要取能取的范围内最远或最近的点，本质上仍然是取最优值思想。
  • 取代价最大/小
    若所有物品最终都必须选择，而选择物品的顺序会影响物品的花费（例如越晚选择花费越大），则可以考虑贪心地优先选花费增长快的物品。
  • 权值计算
    有时候取最大值的对象并不明确，可能需要推式子并化简。例题：保护花朵。

0x0120 适用范围

0x0121 最优子结构

能够使用贪心算法的问题一般都具有“最优子结构”。其含义为：问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。（部分来源：OI-Wiki）

  • 问题能够分解成子问题来解决
    例如，一个序列上的问题，可以先考虑这个序列的一个子段的答案，并扩展到整个区间。
  • 子问题的最优解能递推到最终问题的最优解
    如果一个子问题的最优解一定是全局最优解的一部分，就可以使用贪心。否则，可以考虑求出所有子问题的最优解，并选这些解中最优的扩展，本质上是动态规划的基本思想。

0x0122 常见证明方式

  • 反证法
    如果交换方案中某两个元素不会使答案变得更好，则目前解已经是最优解了。不排除会有“局部最优解”出现，但如果问题具有“最优子结构”就没有这样的情况产生。
  • 归纳法
    由最小的子问题即“边界条件”一步步归纳，最终得出结论。

0x0130 常利用的 STL、算法与 DS

0x0131 取最优

贪心在选择最优解的过程中，如果不需要中途改动（最优解是静态的），则可以考虑先排序再取用。

一般常用 std::sort(begin, end[, compare = less<_Tp>]) 排序，注意其不具有稳定性。为使 sort 排序具有稳定性，可以考虑将唯一编号与权值同时放入一个结构体，并以编号为第二关键字排序。另一种解决方案是 std::stable_sort(begin, end[, compare = less<_Tp>])，其在无多余栈空间时时间复杂度有可能退化为 $O(n \log^2 n)$。其余情况下，两个函数的时间复杂度均为 $O(n \log n)$。

如果有改动（最优解可能是动态的），则需要利用数据结构维护最大值，较简单的问题可以使用堆。

STL 中，有 std::priority_queue<_Tp> 这一包装好的容器，可以用于简便地实现堆。默认行为下，此容器是大根的。

0x0132 维护区间修改与/或区间查询

部分题目中，需要支持区间处理信息。

以下部分内容可在数据结构专题中详细学习。

树状数组 Binary Indexed Tree

正常写法的树状数组，原生支持单点加、前缀求和。若调换修改和查询的写法，可以支持后缀求和。

树状数组一般只能支持具有可减性的操作。利用操作的可减性，可以通过前缀和得知区间和。

特别地，利用差分，可以实现区间修改、单点查询。

复杂度：$O(n \log n)-O(\log n)$

线段树 SeGment Tree

其常数较树状数组大，但其结构决定了其可以解决更多区间问题，包括大部分具有可加性的问题。可以实现所有树状数组能做的操作。

复杂度：$O(n \log n)-O(\log n)$

平衡树

包括 Splay、Treap、FHQ-Treap、文艺平衡树 等等。平衡树一般用于解决与排名相关的问题。

复杂度：$O(n \log n)-O(\log n)$

树套树

较常用的有树状数组套线段树、线段树套线段树、线段树套平衡树。由于树套树内节点较多，而用得到的相对少，所以树套树的所有线段树一般都动态开点。可以解决二维区间或动态区间排名等问题。

复杂度：$O(n \log n)-O(\log^2 n)$，视问题而有所不同。

0x0133 树上贪心

这部分包括一些较快的 LCA 求法，以及树链剖分、LCT、ETT 等较难数据结构。其中较简单的倍增 LCA、树链剖分在提高篇里就会讲到。

0x0140 例题

提高篇的这几道题也没什么说的……

0x0143 喷水装置

涉及到了一点点计算几何。考虑一个喷水装置的喷水区间是可以用勾股定理求的，因此求一下。注意用 double 存储。特别地，当一个喷水装置无法覆盖到区间时，将其左右端点均设为其位置，或者直接忽略。

0x0149 家庭作业

前置：E 智力大冲浪。

考虑 E 题的复杂度瓶颈在于枚举可选位置，这一步是 $O(n)$ 的，本题难以承受。

有两种做法，第一种是将 vis 用链表实现，这样可以 $O(1)$ 查找；第二种是利用 bitset 的小常数及其方法 _Find_next 查询，也可以卡过去，并且跑的很快。

0x014a 钓鱼

也可以考虑使用动态规划。

上一篇
下一篇