贪心¶

引入¶

贪心算法是用计算机来模拟我们人类在面对问题时做出决策的过程的一种算法。并且，它在进行决策的时候总是目光短浅地选择最优的操作，来尽可能地取得最优解。

并不是所有的题目都可以由贪心实现，但是贪心是众多算法的基础。比如搜索中的“最优化剪枝”还有 Dijkstra 算法的中心思想，里面都有一些贪心的元素。

贪心算法往往比较简单，因为人类本身就是贪心的。就比如接下来的一道题：

例题

给定 $n$ 个数，你现在要选择最多 $m$ 个数 $(m \leq n)$ ，使得选择的数相加和最大。输出这个最大的相加和。（可能会有负数）

这个问题，就跟你做作业一样，选择一定数量的作业，那么我们每一次都选择量最少的作业，那么最后选择的作业加起来一定也是最少的。本题也一样，每一次都选择最大的那一个数，那么加起来一定也是最多的。

注意这里可能会有负数，但是加负数是没有用的。那么如果我们加到了负数，就说明后面的数都是负数了，那么我们就不加，直接退出即可。

代码

cin >> n >> m;
for (int i = 1; i <= n; i++) {
  cin >> a[i];
}
sort(a + 1, a + n + 1, greater<>());
for (int i = 1; i <= m; i++) {
  ans += a[i] * (a[i] > 0);
}
return ans;

例题¶

排队接水

现在有 $n$ 个人排队接水，第 $T_{i}$ 个人接水的时间为 $T_{i}$ 。现在要你重新排列这 $n$ 个人的位置，使得 $n$ 个人的平均等待时间最少。输出重新排列后的顺序以及平均等待时间。

首先，看到这题，我们的人脑很快就可以想出一个解法：叫打水更快的人站到前面不就行了，这样子后面的人等的不叫少了吗？可是，这个解法怎么证明是对的呢？

我们可以设总的打水时间为 $S$ 。显然， $S$ 越小最后的平均等待时间也会越小，因此我们需要最小化 $S$ 。因为第 $i$ 个人需要等待前面人和自己打水的所有时间，那么第 $i$ 个人就需要等待 $\sum_{j = 1}^{i} a_{j}$ 的时间，所以 $S = \sum_{i = 1}^{n} \sum_{j = 1}^{i} T_{j}$ 。

我们发现， $T_{1}$ 需要相加 $n$ 次， $T_{2}$ 需要相加 $n - 1$ 次…… $T_{n}$ 却只要相加 $1$ 次。因此，我们就需要把时间短的排在前面。这样子就是最优的。

代码

struct Node {
  int v, id;
};

cin >> n >> m;
for (int i = 1; i <= n; i++) {
  cin >> a[i].v;
  a[i].id = i;
}
sort(a + 1, a + n + 1, [](const Node &a, const Node &b) {
  return a.v < b.v;
});
for (int i = 1; i <= n; i++) {
  cout << a[i].id << ' ';
  sum += a[i].v * (n - i + 1);
}
cout << sum / n << '\n';

合并果子

现在有 $n$ 堆果子，第 $i$ 堆果子的重量为 $a_{i}$ 。每一次你可以选择两队不同的果子进行合并，耗费的力气就是这两堆果子的重量之和。问你最少需要多少的重量才能使得 $n$ 堆果子最终合成一堆？

首先，看到这题道题目，相信你和我一样，一下子就想到了每一次都合并最轻的两堆果子。但是这样子求解到底对不对呢？

很显然，合并了一堆果子之后，虽然看起来他们已经成为了一堆果子，但是底层上还是分开起来相加了。我们一共需要合并 $n - 1$ 次，那么肯定会有果子正好合并 $n - 1$ 次，也有果子只合并了 $1$ 次。我们想要让答案最小就需要把 $a_{i}$ 较大的果子尽量少合并， $a_{i}$ 较小的果子尽量多合并。这样子最后的答案就也是最小的了。

既然这个算法是对的，那么我们每一次合并了之后都排序，然后把最小的合并，最后就可以算出答案来……了吗？这题显然 $n$ 较小，但是万一 $n$ 达到了 $10^{5}$ 呢？

其实我们可以使用堆这个数据结构。它可以以 $O (\log_{2} n)$ 取出或删除最小/最大值。由于 STL 里面已经提供了优先队列这个预定义的堆了，因此这里不在过多讲解。Priority Queue 的具体使用方法和堆这个数据结构的具体信息请参阅本站的其他文章。

代码

priority_queue<int, vector<int>, greater<>> q;  // C++11 之前需要在尖括号之间空一格

cin >> n;
for (int i = 1, x; i <= n; i++) {
  cin >> x;
  q.push(x);
}
for (int a, b; q.size() > 1; q.push(a + b)) {
  a = q.top(), q.pop();
  b = q.top(), q.pop();
  ans += a + b;
}
cout << ans << '\n';

贪心¶

引入¶

例题¶

评论