什么是贪心
在每次决策的时候都采取当前意义下的最优策略，一般贪心问题的难点在于最优策略的选择。
例题：有 \(n\) 项工作，每项工作从 \(s_i\) 时间开始，\(t_i\) 时间结束，对于每项工作你都可以选择是否要参加，若参加则必须全程参与。那么在不能同时参与多个工作的情况下，最多可以参加几个工作？（\(n \le 10^5; s_i,t_i \le 10^9\)）
懒狗策略（错误）
时间越长的工作越耽误时间，那么考虑按照工作时长排序，先选择做工作时间短的。
反例：(1, 4), (3, 5), (4, 7) 三个工作，按照这个策略会优先选择 (3, 5) 这个工作，从而剩下的工作都做不了了；而实际上最好的方案是做 (1, 4) 和 (4, 7) 这两个工作。
卷王策略（错误）
开始工作得越早，就能做更多的工作，考虑按照 \(s_i\) 排序，先做开始时间造的工作。
反例：(1, 10), (3, 5), (7, 9) 三个工作，按照这个策略会优先选择 (1, 10) 这个工作，从而剩下的工作都做不了了；而实际上最好的方案是做 (3, 5) 和 (7, 9) 这两个工作。
正确策略
按照 \(t_i\) 排序，先做结束时间早的。
证明：优先考虑结束时间可以在选择工作数量相同的情况下，为后续的选择提供更多的时间。
例：P1090 [NOIP2004 提高组] 合并果子
解题思路
不难发现，每次合并最小的两堆果子就是最优的选择。所以我们可以把所有的果子数目都放到一个小根堆里，每次掏出最小的两堆，计入答案后再把这两堆合并后的数量放回堆中。
例：CF1768C Elemental Decompress
题意：给定一个序列 \(a\)，请构造两个排列 \(p, q\)，使得 \(a_i = \max (p_i, q_i)\)，可能无解。
数据范围：\(n \le 200000\)
解题思路
可以按照 \(a[i]\) 的大小，按从大到小的顺序依次填数。
比如 \(a = [5, 3, 4, 2, 5]\)
首先填第一个数和第五个数（\(5\) 最大），因为要使得 \(a\) 中两个位置为 \(5\)，所以不妨让 \(p[1] = 5, q[5] = 5\)
接着填第三个数，只需要一个 \(4\)，不妨让 \(p[3] = q[3] = 4\)
同理，让 \(p[2] = q[2] = 3, p[4] = q[4] = 2\)，此时 \(p\) 和 \(q\) 的一部分位置已经填过数字，还剩一些数字没有使用；
重复从大到小的填数顺序，将 \(p\) 和 \(q\) 中剩余的数也同样从大到小把一开始没填的位置填上，因此 \(p[5] = 1, q[1] = 1\)
注意按以上策略填完数字后还需要重新检查一遍是否满足要求，不满足说明无解。
参考代码
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 200005;
int a[N], p[N], q[N];
bool u1[N], u2[N];
vector<int> idx[N];
int main()
{
int t;
scanf("%d", &t);
while (t--) {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
idx[i].clear(); p[i] = q[i] = 0;
u1[i] = u2[i] = false;
}
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
idx[a[i]].push_back(i);
}
bool flag = true;
for (int i = n; i >= 1; i--) {
if (idx[i].size() > 2) {
flag = false; break;
}
if (idx[i].size() == 2) {
p[idx[i][0]] = i; q[idx[i][1]] = i;
u1[i] = u2[i] = true;
} else if (idx[i].size() == 1) {
p[idx[i][0]] = q[idx[i][0]] = i;
u1[i] = u2[i] = true;
}
}
if (!flag) {
printf("NO\n"); continue;
}
int num1 = n, num2 = n;
for (int i = n; i >= 1; i--) {
if (idx[i].size() == 2) {
int i1 = idx[i][0], i2 = idx[i][1];
while (num1 >= 0 && u1[num1]) num1--;
p[i2] = num1; u1[num1] = true;
while (num2 >= 0 && u2[num2]) num2--;
q[i1] = num2; u2[num2] = true;
}
}
for (int i = 1; i <= n; i++)
if (a[i] != max(p[i], q[i])) {
flag = false; break;
}
if (flag) {
printf("YES\n");
for (int i = 1; i <= n; i++) printf("%d%c", p[i], i == n ? '\n' : ' ');
for (int i = 1; i <= n; i++) printf("%d%c", q[i], i == n ? '\n' : ' ');
} else printf("NO\n");
}
return 0;
}
例：CF1779C Least Prefix Sum
题意：给定 \(n\) 个数，每次修改可以让一个数乘以 \(-1\)，求最少操作次数使得前 \(m\) 个数的和是所有前缀和中最小的。
数据范围：\(m \le n \le 200000\)
解题思路
首先转换题意：
若 \(i<m\)，则前 \(i\) 个数的和等于前 \(m\) 个数的和减去第 \(i+1\) 到第 \(m\) 个数的和；
若 \(i>m\)，则前 \(i\) 个数的和等于前 \(m\) 个数的和加上第 \(m+1\) 到第 \(i\) 个数的和。
所以题目等价于要求，在修改后，前 \(m\) 个数的所有后缀和都不大于 \(0\)（第 \(1 \sim m\) 个数的和可以大于 \(0\)）；第 \(m+1\) 到第 \(n\) 个数的所有前缀和都不小于 \(0\)
当前 \(m\) 个数的某个后缀和大于 \(0\) 时，显然这时我们应该去修改最大的正数；当第 \(m+1\) 到第 \(n\) 个数的某个前缀和小于 \(0\) 时，显然这时我们应该去修改最小的负数；以上操作可以通过大根堆与小根堆来维护当前的数。
参考代码
#include <cstdio>
#include <queue>
using namespace std;
typedef long long LL;
const int N = 200005;
int a[N];
int main()
{
int t;
scanf("%d", &t);
while (t--) {
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
int ans = 0;
LL sum = 0;
priority_queue<int> q1;
for (int i = m; i > 1; i--) {
q1.push(a[i]); sum += a[i];
if (sum > 0) {
ans++;
int x = q1.top();
sum -= x; q1.pop();
sum -= x; q1.push(-x);
}
}
sum = 0;
priority_queue<int, vector<int>, greater<int>> q2;
for (int i = m + 1; i <= n; i++) {
q2.push(a[i]); sum += a[i];
if (sum < 0) {
ans++;
int x = q2.top();
sum -= x; q2.pop();
sum -= x; q2.push(-x);
}
}
printf("%d\n", ans);
}
return 0;
}
例：P1016 [NOIP1999 提高组] 旅行家的预算
难点：不知道每一站加油加多少，少了怕不够，多了怕浪费。
解题思路
考虑“退油”这个操作，前面买的油可以在任何地方以原价退款（等价于当初没买油）。这样我们在行驶过程中尽量使用便宜的油，每到一个加油站把所有比当前油价贵的油退掉，再把油箱装满。（这里的退油和加油操作用单调队列实现可以达到线性复杂度）
这题的数据大多是小数，注意精度问题。
参考代码
#include <cstdio>
#include <deque>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 10;
const double EPS = 1e-6;
struct Station {
double d, p;
bool operator<(const Station& other) const {
return d != other.d ? d < other.d : p < other.p;
}
};
Station s[N];
struct Oil {
double p, v;
};
int main()
{
double d1, c, d2, p;
int n;
scanf("%lf%lf%lf%lf%d", &d1, &c, &d2, &p, &n);
for (int i = 1; i <= n; i++) scanf("%lf%lf", &s[i].d, &s[i].p);
sort(s + 1, s + n + 1);
double cur = 0, ans = 0;
deque<Oil> dq;
dq.push_back({p, c});
bool flag = true;
for (int i = 1; i <= n; i++) {
if (s[i].d > d1 - EPS) break;
double need = (s[i].d - cur) / d2;
while (!dq.empty()) {
if (dq.front().v > need - EPS) {
ans += dq.front().p * need;
dq.front().v -= need; need = 0;
break;
} else {
ans += dq.front().p * dq.front().v;
dq.pop_front(); need -= dq.front().v;
}
}
if (need > EPS) {
flag = false;
break;
}
double vol = (s[i].d - cur) / d2;
cur = s[i].d;
while (!dq.empty() && dq.back().p > s[i].p + EPS) {
vol += dq.back().v; dq.pop_back();
}
dq.push_back({s[i].p, vol});
}
double need = (d1 - cur) / d2;
while (!dq.empty()) {
if (dq.front().v > need - EPS) {
ans += dq.front().p * need; need = 0;
break;
} else {
ans += dq.front().p * dq.front().v; need -= dq.front().v;
dq.pop_front();
}
}
if (need > EPS) flag = false;
if (!flag) printf("No Solution\n");
else printf("%.2f\n", ans);
return 0;
}
例：P1080 [NOIP2012 提高组] 国王游戏
解题思路
假设我们现在已经有了一个排列顺序
大臣左手的数字为 \(A[1] \sim A[n]\)，右手的数字为 \(B[1] \sim B[n]\)，国王的数字为 \(A[0], B[0]\)
考虑交换位置为 \(i, i+1\) 两位大臣的位置
交换前：两人的奖赏分别为 \(\frac{1}{B[i]} \prod \limits_{j=0}^{i-1} A[j]\) 和 \(\frac{A[i]}{B[i+1]} \prod \limits_{j=0}^{i-1} A[j]\)
交换后：两人的奖赏分别为 \(\frac{1}{B[i+1]} \prod \limits_{j=0}^{i-1} A[j]\) 和 \(\frac{A[i+1]}{B[i]} \prod \limits_{j=0}^{i-1} A[j]\)
其余大臣的奖赏不变
提取公因式后，发现交换前为 \(\max(\frac{1}{B[i]}, \frac{A[i]}{B[i+1]})\)，交换后则为 \(\max(\frac{1}{B[i+1]}, \frac{A[i+1]}{B[i]})\)
两式同乘 \(B[i]*B[i+1]\) 后，只要比较 \(\max(B[i+1], A[i]*B[i])\) 和 \(max(B[i], A[i+1]*B[i+1])\)，等价于比较 \(A[i]*B[i]\) 和 \(A[i+1]*B[i+1]\)
当前者大于后者时，应当进行交换使得结果更优（获得奖赏最多的大臣，所获奖赏尽可能的少）
参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
const int LEN = 5000;
struct Person {
int a, b;
bool operator<(const Person& other) const {
return max(other.b, a * b) < max(b, other.a * other.b);
}
};
Person p[N];
vector<int> ans, cur, tmp1, tmp2, tmp;
void print_bigint(vector<int>& v) {
int len = int(v.size()) - 1;
for (int i = len; i >= 0; --i) printf("%d", v[i]);
printf("\n");
}
vector<int> mul(vector<int>& a, vector<int>& b) {
vector<int> ret;
ret.clear();
int la = a.size(), lb = b.size();
ret.resize(la + lb);
for (int i = 0; i < la; ++i)
for (int j = 0; j < lb; ++j) {
ret[i + j] += a[i] * b[j];
if (ret[i + j] >= 10) {
ret[i + j + 1] += ret[i + j] / 10;
ret[i + j] %= 10;
}
}
int len = int(ret.size()) - 1;
while (len > 0 && ret[len] == 0) {
ret.pop_back();
--len;
}
return ret;
}
bool greater_eq(vector<int>& a, vector<int>& b, int last_dg) {
int la = a.size(), lb = b.size();
if (last_dg + lb < la && a[last_dg + lb]) return true;
for (int i = 0; i < lb; ++i) {
int x = a[last_dg + lb - i - 1];
int y = b[lb - i - 1];
if (x != y) return x > y;
}
return true;
}
vector<int> div(vector<int> a, vector<int>& b) {
int la = a.size(), lb = b.size();
if (la < lb) return vector<int>(1);
vector<int> res;
res.clear();
res.resize(la - lb + 1);
int cur = la - lb;
for (int i = cur; i >= 0; --i) {
while (greater_eq(a, b, i)) {
for (int j = 0; j < lb; ++j) {
a[i + j] -= b[j];
if (a[i + j] < 0) {
a[i + j] += 10;
--a[i + j + 1];
}
}
++res[i];
}
}
int len = int(res.size()) - 1;
while (len > 0 && res[len] == 0) {
res.pop_back();
--len;
}
return res;
}
vector<int> convert(int x) {
if (x == 0) return vector<int>(1);
vector<int> res;
while (x > 0) {
res.push_back(x % 10);
x /= 10;
}
return res;
}
bool bigint_greater(vector<int>& a, vector<int>& b) {
int la = a.size(), lb = b.size();
if (la != lb) return la > lb;
for (int i = la - 1; i >= 0; --i)
if (a[i] != b[i]) return a[i] > b[i];
return false;
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 0; i <= n; ++i) {
scanf("%d%d", &p[i].a, &p[i].b);
}
sort(p + 1, p + n + 1);
cur = convert(p[0].a);
ans.resize(1);
for (int i = 1; i <= n; ++i) {
tmp1 = convert(p[i].a);
tmp2 = convert(p[i].b);
tmp = div(cur, tmp2);
if (bigint_greater(tmp, ans)) ans = tmp;
cur = mul(cur, tmp1);
}
print_bigint(ans);
return 0;
}
在运用贪心算法时，有时候贪心策略并不容易判断；而在有时候，虽然想到了某些贪心策略，但其正确性并不容易证明，需要大胆猜测！
例：P1248 加工生产调度
此题较难，其结论可以记一下。
如何贪心？
- 根据 \(A_i\) 升序？
- 根据 \(B_i\) 降序？
- 根据 \(A_i - B_i\) 升序？
- 前半段根据 \(A_i\) 升序，后半段根据 \(B_i\) 降序？
为了要使总的空闲时间最少，就要先加工 \(A_i\) 小的，最后加工 \(B_i\) 小的产品
贪心策略
先做 \(A_i < B_i\) 的产品，并将这些产品按 \(A_i\) 升序排序，之后再做 \(A_i \ge B_i\) 的产品，并将这些产品按 \(B_i\) 降序排序
参考代码
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1005;
int sign(int x) {
return x > 0 ? 1 : (x == 0 ? 0 : -1);
}
struct Product {
int a, b, id;
bool operator<(const Product& other) const {
int s1 = sign(a - b), s2 = sign(other.a - other.b);
if (s1 != s2) return s1 < s2;
if (s1 < 0) return a < other.a;
else return b > other.b;
}
};
Product p[N];
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &p[i].a); p[i].id = i;
}
for (int i = 1; i <= n; i++) scanf("%d", &p[i].b);
sort(p + 1, p + n + 1);
int time_a = 0, time_b = 0;
for (int i = 1; i <= n; i++) {
time_a += p[i].a;
time_b = max(time_a, time_b) + p[i].b;
}
printf("%d\n", time_b);
for (int i = 1; i <= n; i++) printf("%d%c", p[i].id, i == n ? '\n' : ' ');
return 0;
}