"NOIP 2012 国王游戏open in new window" 恰逢 H 国国庆，国王邀请 n 位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这 n 位大臣排成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。

国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。注意，国王的位置始终在队伍的最前面。

"解题思路"

设排序后第 $i$ 个大臣左右手上的数分别为 $a_i, b_i$ 。考虑通过邻项交换法推导贪心策略。

用 $s$ 表示第 $i$ 个大臣前面所有人的 $a_i$ 的乘积，那么第 $i$ 个大臣得到的奖赏就是 $\dfrac{s} {b_i}$ ，第 $i + 1$ 个大臣得到的奖赏就是 $\dfrac{s \cdot a_i} {b_{i+1}}$ 。

如果我们交换第 $i$ 个大臣与第 $i + 1$ 个大臣，那么此时的第 $i$ 个大臣得到的奖赏就是 $\dfrac{s} {b_{i+1}}$ ，第 $i + 1$ 个大臣得到的奖赏就是 $\dfrac{s \cdot a_{i+1}} {b_i}$ 。

如果交换前更优当且仅当

\max \left(\dfrac{s} {b_i}, \dfrac{s \cdot a_i} {b_{i+1}}\right) < \max \left(\dfrac{s} {b_{i+1}}, \dfrac{s \cdot a_{i+1}} {b_i}\right)

提取出相同的 $s$ 并约分得到

\max \left(\dfrac{1} {b_i}, \dfrac{a_i} {b_{i+1}}\right) < \max \left(\dfrac{1} {b_{i+1}}, \dfrac{a_{i+1}} {b_i}\right)

然后分式化成整式得到

\max (b_{i+1}, a_i\cdot b_i) < \max (b_i, a_{i+1}\cdot b_{i+1})

实现的时候我们将输入的两个数用一个结构体来保存并重载运算符：

struct uv {
    int a, b;

    bool operator<(const uv &x) const {
    return max(x.b, a * b) < max(b, x.a * x.b);
    }
};

后悔法的例题

"「USACO09OPEN」工作调度 Work Schedulingopen in new window" 约翰的工作日从 $0$ 时刻开始，有 $10^9$ 个单位时间。在任一单位时间，他都可以选择编号 $1$ 到 $N$ 的 $N(1 \leq N \leq 10^5)$ 项工作中的任意一项工作来完成。工作 $i$ 的截止时间是 $D_i(1 \leq D_i \leq 10^9)$ ，完成后获利是 $P_i( 1\leq P_i\leq 10^9 )$ 。在给定的工作利润和截止时间下，求约翰能够获得的利润最大为多少。

"解题思路" 1. 先假设每一项工作都做，将各项工作按截止时间排序后入队； 2. 在判断第 i 项工作做与不做时，若其截至时间符合条件，则将其与队中报酬最小的元素比较，若第 i 项工作报酬较高（后悔），则 ans += a[i].p - q.top()。
用优先队列（小根堆）来维护队首元素最小。 3. 当 a[i].d<=q.size() 可以这么理解从 0 开始到 a[i].d 这个时间段只能做 a[i].d 个任务，而若 q.size()>=a[i].d 说明完成 q.size() 个任务时间大于等于 a[i].d 的时间，所以当第 i 个任务获利比较大的时候应该把最小的任务从优先级队列中换出。

"参考代码"
C++

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;

struct f {
  long long d;
  long long p;
} a[100005];

bool cmp(f A, f B) { return A.d < B.d; }

priority_queue<long long, vector<long long>, greater<long long> >
    q;  // 小根堆维护最小值

int main() {
  long long n, i;
  cin >> n;
  for (i = 1; i <= n; i++) {
    scanf("%lld%lld", &a[i].d, &a[i].p);
  }
  sort(a + 1, a + n + 1, cmp);
  long long ans = 0;
  for (i = 1; i <= n; i++) {
    if (a[i].d <= (int)q.size()) {  // 超过截止时间
      if (q.top() < a[i].p) {       // 后悔
        ans += a[i].p - q.top();
        q.pop();
        q.push(a[i].p);
      }
    } else {  // 直接加入队列
      ans += a[i].p;
      q.push(a[i].p);
    }
  }
  cout << ans << endl;
  return 0;
}

Python

from collections import defaultdict
from heapq import heappush, heappop

a = defaultdict(list)
for _ in range(int(input())):
    d, p = map(int, input().split())
    a[d].append(p)  # 存放对应时间的收益

ans = 0  # 记录总收益
q = []  # 小根堆维护最小值
l = sorted(a.keys(), reverse=True)
for i, j in zip(l, l[1:] + [0]):
    for k in a.pop(i):
        heappush(q, ~k)
    for _ in range(i - j):
        if q:  # 从堆中取出收益最多的工作
            ans += ~heappop(q)
        else:  # 堆为空时退出循环
            break
print(ans)

复杂度分析

空间复杂度：当输入 $n$ 个任务时使用 $n$ 个 $a$ 数组元素，优先队列中最差情况下会储存 $n$ 个元素，则空间复杂度为 $O(n)$ 。
时间复杂度：std::sort 的时间复杂度为 $O(n\log n)$ ，维护优先队列的时间复杂度为 $O(n\log n)$ ，综上所述，时间复杂度为 $O(n\log n)$ 。

习题

参考资料与注释

贪心算法 - 维基百科，自由的百科全书open in new window ↩︎

贪心

贪心

引入

解释

适用范围

证明

要点

常见题型

排序解法

后悔解法

区别

与动态规划的区别

例题详解

邻项交换法的例题

后悔法的例题

复杂度分析

习题

参考资料与注释