#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, a[N], ans, w;
int main() {
cin >> n >> w;
for (int i = 1; i <= n; i++)
cin >> a[i];
sort(a + 1, a + 1 + n);
int tmp = 0;
for (int i = 1; i <= n; i++) {
if (tmp + a[i] <= w) {
tmp += a[i];
ans++;
} else break;
}
cout << ans;
return 0;
}
部分背包问题
P2240 部分背包问题
优先选择单位价值最高的
#include <bits/stdc++.h>
using namespace std;
const int N = 1e2 + 10;
struct node {
int value, weight;
double ave;
bool operator < (node t) {
return ave > t.ave;
}
};
node a[N];
int n, t;
double ans;
int main() {
cin >> n >> t;
for (int i = 1; i <= n; i++) {
cin >> a[i].weight >> a[i].value;
a[i].ave = a[i].value * 1.0 / a[i].weight;
}
sort(a + 1, a + 1 + n);
for (int i = 1; i <= n; i++) {
if (t >= a[i].weight)
ans += a[i].value, t -= a[i].weight;
else {
ans += a[i].ave * t;
break;
}
}
printf("%.2lf", ans);
return 0;
}
乘船问题
P1094 纪念品分组
贪心策略：最轻的人和最重的人配对
#include <bits/stdc++.h>
using namespace std;
const int N = 3e4 + 10;
int n, w, a[N];
int ans;
int main() {
cin >> w >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
sort(a + 1, a + 1 + n);
int l = 1, r = n;
while (l <= r) {
if (a[l] + a[r] <= w)
l++, r--;
else r--;
ans++;
}
cout << ans;
return 0;
}
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
// pair 对 结束时间(first)，开始时间(second)
pair<int, int> a[N];
int n, ans;
int main() {
freopen("huodong.in", "r", stdin);
freopen("huodong.out", "w", stdout);
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i].second >> a[i].first;
sort(a + 1, a + 1 + n);
ans = 1;
int last = a[1].first;
for (int i = 2; i <= n; i++) {
if (a[i].second >= last) {
ans++;
last = a[i].first;
}
}
cout << ans;
return 0;
}
区间选点问题
给定 n 个区间 [ai,bi] ， 在数轴上选尽量少的点，使得每个区间内都至少有一个点(不同区间内含的点可以是一个)
贪心策略：按照结束为止从小到大排序，然后从区间 1 到区间 n 进行选择：对于当前区间，若集合中的数不能覆盖它，则将区间末尾的数加入集合中
#include <bits/stdc++.h>
using namespace std;
const int N = 3e4 + 10;
struct node {
int b, e, t;
bool operator < (node a) {
return e < a.e;
return b > a.b;
}
};
int n, h, ans;
bool vis[N];
node a[5005];
int main() {
cin >> n >> h;
for (int i = 0; i < h; i++)
cin >> a[i].b >> a[i].e >> a[i].t;
sort(a, a + h);
for (int i = 0; i < h; i++) {
int t = a[i].t;
for (int j = a[i].b; j <= a[i].e; j++) {
if (vis[j]) t--;
if (t == 0) break;
}
for (int j = a[i].e; t; j--) {
if (vis[j] == 1) continue;
t--;
vis[j] = 1;
ans++;
}
}
cout << ans;
return 0;
}
区间覆盖问题
给 n 个区间 [ai,bi] ，选择尽量少的区间覆盖一条指定的线段区间 [s,t]
将所有的区间按左端点从小到大排序，依次处理每个区间。每次选择覆盖点 s 的区间中右端点坐标最大的一个点，并将 s 更新为该区间的右端点坐标，直到选择的区间已包含了 t 为止
贪心策略： 在某个时刻的 s , 找一个满足 a[i]<=s 的 b[i] 的最大值即可
18118. 喷水装置
#include <bits/stdc++.h>
using namespace std;
int n, cnt, L, h, x, r;
struct node {
double x, y;
} ;
node a[20005];
bool cmp(node x, node y) {
return x.x < y.x;
}
int main() {
int t;
cin >> t;
while (t--) {
cin >> n >> L >> h;
cnt = 0;
for (int i = 1; i <= n; i++) {
cin >> x >> r;
if (r <= h / 2)
continue; //喷水装置不能覆盖草坪宽度
cnt++;
a[cnt].x = x - sqrt(r * r - h * h / 4.0);
a[cnt].y = x + sqrt(r * r - h * h / 4.0);
}
sort(a + 1, a + 1 + cnt, cmp);
double t = 0;
int ans = 0, bj = 1, i = 1;
while (t < L) {
ans++;
double s = t;
for (; a[i].x <= s && i <= cnt; i++) //依次找能够覆盖L点的最大右端点
if (t < a[i].y)
t = a[i].y;
if (t == s && s < L) {
cout << -1 << endl;
bj = 0;
break;
}
}
if (bj)
cout << ans << endl;
}
return 0;
}
流水作业调度问题
有 n 个作业要在两台机器 M1 和 M2 组成的流水线上完成加工。每个作业 i 都必须先花时间 ai 在 M1 上加工，然后花时间 bi 在M2 上加工
确定 n 个作业的加工顺序，使得从作业 1 在机器 M1 上加工开始到作业 n 在机器 M2 上加工完为止所用的总时间最短
// 贪心策略，按照 左手*右手
// 从小到大排序
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
#define int long long
struct node {
int l, r;
};
bool cmp(node a, node b) {
return a.r * a.l < b.r * b.l;
}
// t 来表示左手的乘积
int n, ans, t;
node a[N];
signed main() {
cin >> n;
for (int i = 0 ; i <= n; i++)
cin >> a[i].l >> a[i].r;
// 国王不参与排序
sort( a+1 , a+1+n , cmp);
t = a[0].l; // 左手的乘积
for (int i = 1; i <= n; i++) {
ans = max(ans, t / a[i].r);
t = t * a[i].l;
}
cout << ans;
return 0;
}
证明： 决策包容性
做出局部最优决策后以后，在问题状态空间的可达集合中包含了做出其他任何决策后的可达集合
换言之，这个局部最优策略提供的可能性包含了其他所有策略提供的可能性
P2887 Sunscreen G
贪心策略：按照 min SPF递减的顺序把奶牛排序，然后依次在防晒霜里面找 SPF 值最大的使用
证明：
因为奶牛已经按照minSPF 的顺序递减排序，所有每一个不低于当前奶牛
minSPF 值的防晒霜，都不会低于后面其他奶牛的 minSPF
对于当前奶牛可用的任意两瓶防晒霜 x 和 y,如果SPF[X] < SPF[y]
那么后面其他奶牛只可能出现 x,y都能用或者x,y都不能用，或者x能用y不能用，所以 x 的适用范围更广
综上，尽量满足当前的奶牛，并选择 SPF 值尽量大的是最优选择
int n, m, ans;
struct node {
int spf, cnt;
};
bool cmp(node a, node b) {
return a.spf > b.spf;
}
struct node1 {
int l, r;
};
bool cmp1(node1 a, node1 b) {
if (a.l != b.l) return a.l > b.l;
return a.r > b.r;
}
node1 a[N];
node b[N];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> a[i].l >> a[i].r;
for (int i = 1; i <= m; i++)
cin >> b[i].spf >> b[i].cnt;
// 按照 minSPF 递减的顺序排序
sort(a + 1, a + 1 + n, cmp1);
// 按照 SPF 递减的顺序排序
sort(b + 1, b + 1 + m, cmp);
// 遍历所有的奶牛
for (int i = 1; i <= n; i++) {
// 遍历所有的防晒霜
for (int j = 1; j <= m; j++) {
if (a[i].l <= b[j].spf && a[i].r >= b[j].spf && b[j].cnt) {
ans++, b[j].cnt--;
break;
}
}
}
cout << ans;
return 0;
}
先假设每一项工作都做，将各项工作按截止时间排序后入队；
在判断第 i 项工作做与不做时，若其截至时间符合条件，
则将其与队中报酬最小的元素比较，若第 i 项工作报酬较高（后悔），
则 ans += a[i].p - q.top()。
用优先队列（小根堆）来维护队首元素最小。
当 a[i].d<=q.size() 可以这么理解从 0 开始到 a[i].d 这个时间段只能做 a[i].d 个任务，
而若 q.size()>=a[i].d 说明完成 q.size() 个任务时间大于等于 a[i].d 的时间，
所以当第 i 个任务获利比较大的时候应该把最小的任务从优先级队列中换出
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n;
// pair<时间， 收益>
pair<int, int > a[N];
long long ans;
// 存储相反数，最小值
priority_queue<int> q;
int main() {
cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i].first >> a[i].second;
sort(a, a + n);
for (int i = 0; i < n; i++) {
int t = a[i].first;
if (t <= (int)q.size()) { // 当前时间已经被占用了
// 反悔了，有了更好的选择
if (a[i].second > -(q.top())) { // 队列里面最小的没有当前的优秀
ans += a[i].second - (-q.top());
q.pop();
q.push(-a[i].second);
}
} else {
ans += a[i].second;
q.push(-a[i].second);
}
}
cout << ans;
return 0;
}
---------
# 贪心
- 贪心是一种在每次决策时采取 **当前意义下最优策略的算法** ，使用贪心法要求问题的 **整体最优性可以由局部最优性导出** 。
- 贪心算法的正确性需要证明，常见手法如下：
1. **微扰（邻项交换）**
- 证明在任意局面下，任何对局部最优策略的微小改变都会造成整体结果变差。经常用以 **"排序"** 为贪心策略的证明
2. **决策包容性**
- 证明在任意局面下，做出局部最优决策以后，在问题状态空间中的可达集合包含了做出其他任何决策后的可达集合。换言之，这个局部最优策略提供的可能性包含其他所有策略提供的可能性
3. **决策范围扩展**
- 有时候不容易直接证明局部最优策略的正确性。此时可以往后多扩展一步，有助于我们对局部最优决策进行验证（验证时可以综合使用其他手法）
4. **反证法**
5. **数学归纳法**
## 最优装载问题
- 给 $n$ 个物品，第 $i$ 个物体重量为 $w_i$ , 选择尽量多的物体，使得总重量不超过 $C$
- 重量从小到大排序，依次选择每个物体，直到装不下为止
- 贪心策略：先装最轻的
- ```c++
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, a[N], ans, w;
int main() {
cin >> n >> w;
for (int i = 1; i <= n; i++)
cin >> a[i];
sort(a + 1, a + 1 + n);
int tmp = 0;
for (int i = 1; i <= n; i++) {
if (tmp + a[i] <= w) {
tmp += a[i];
ans++;
} else break;
}
cout << ans;
return 0;
}
```
## 部分背包问题
- P2240 部分背包问题
- 优先选择单位价值最高的
- ```c++
#include <bits/stdc++.h>
using namespace std;
const int N = 1e2 + 10;
struct node {
int value, weight;
double ave;
bool operator < (node t) {
return ave > t.ave;
}
};
node a[N];
int n, t;
double ans;
int main() {
cin >> n >> t;
for (int i = 1; i <= n; i++) {
cin >> a[i].weight >> a[i].value;
a[i].ave = a[i].value * 1.0 / a[i].weight;
}
sort(a + 1, a + 1 + n);
for (int i = 1; i <= n; i++) {
if (t >= a[i].weight)
ans += a[i].value, t -= a[i].weight;
else {
ans += a[i].ave * t;
break;
}
}
printf("%.2lf", ans);
return 0;
}
```
## 乘船问题
- P1094 纪念品分组
- 贪心策略：最轻的人和最重的人配对
- ```c++
#include <bits/stdc++.h>
using namespace std;
const int N = 3e4 + 10;
int n, w, a[N];
int ans;
int main() {
cin >> w >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
sort(a + 1, a + 1 + n);
int l = 1, r = n;
while (l <= r) {
if (a[l] + a[r] <= w)
l++, r--;
else r--;
ans++;
}
cout << ans;
return 0;
}
```
## 选择不相交区间问题
- 给定 $n$ 个开区间 $(a_i , b_i)$ ,选择尽量多个区间，使得这些区间两两没有公共交点
- **18041活动安排**
- 贪心策略：按照结束时间从小到大排序，依次考虑各个区间，如果没有和已经选择的区间冲突，就选择；否则就不选
- 证明：决策包容性：在任意局面下，做出局部最优决策以后，在问题状态空间中的可达集合包含了做出其他任何决策后的可达集合。换言之，这个局部最优策略提供的可能性包含其他所有策略提供的可能性
- ```c++
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
// pair 对 结束时间(first)，开始时间(second)
pair<int, int> a[N];
int n, ans;
int main() {
freopen("huodong.in", "r", stdin);
freopen("huodong.out", "w", stdout);
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i].second >> a[i].first;
sort(a + 1, a + 1 + n);
ans = 1;
int last = a[1].first;
for (int i = 2; i <= n; i++) {
if (a[i].second >= last) {
ans++;
last = a[i].first;
}
}
cout << ans;
return 0;
}
```
## 区间选点问题
- 给定 $n$ 个区间 $[a_i , b_i]$ ， 在数轴上选尽量少的点，使得每个区间内都至少有一个点(不同区间内含的点可以是一个)
- 贪心策略：按照结束为止从小到大排序，然后从区间 $1$ 到区间 $n$ 进行选择：对于当前区间，若集合中的数不能覆盖它，则将区间末尾的数加入集合中
- 
- **P1250. 种树**
- 树要种得少，就要使一棵树能给多个区间使用，尽量在重叠区间种树即可，重叠位置一定是在区间尾部
- 按照区间的结束位置排序，之后依次处理每个区间，先在第一个区间尾部种上满足要求的树，下一个区间差多少棵就在该区间尾部种多少棵
- ```c++
#include <bits/stdc++.h>
using namespace std;
const int N = 3e4 + 10;
struct node {
int b, e, t;
bool operator < (node a) {
return e < a.e;
return b > a.b;
}
};
int n, h, ans;
bool vis[N];
node a[5005];
int main() {
cin >> n >> h;
for (int i = 0; i < h; i++)
cin >> a[i].b >> a[i].e >> a[i].t;
sort(a, a + h);
for (int i = 0; i < h; i++) {
int t = a[i].t;
for (int j = a[i].b; j <= a[i].e; j++) {
if (vis[j]) t--;
if (t == 0) break;
}
for (int j = a[i].e; t; j--) {
if (vis[j] == 1) continue;
t--;
vis[j] = 1;
ans++;
}
}
cout << ans;
return 0;
}
```
## 区间覆盖问题
- 给 $n$ 个区间 $[a_i, b_i]$ ，选择尽量少的区间覆盖一条指定的线段区间 $[s,t]$
- 将所有的区间按左端点从小到大排序，依次处理每个区间。每次选择覆盖点 $s$ 的区间中右端点坐标最大的一个点，并将 $s$ 更新为该区间的右端点坐标，直到选择的区间已包含了 $t$ 为止
- 贪心策略： 在某个时刻的 $s$ , 找一个满足 $a[i]<= s$ 的 $b[i]$ 的最大值即可
- **18118. 喷水装置**
- ```c++
#include <bits/stdc++.h>
using namespace std;
int n, cnt, L, h, x, r;
struct node {
double x, y;
} ;
node a[20005];
bool cmp(node x, node y) {
return x.x < y.x;
}
int main() {
int t;
cin >> t;
while (t--) {
cin >> n >> L >> h;
cnt = 0;
for (int i = 1; i <= n; i++) {
cin >> x >> r;
if (r <= h / 2)
continue; //喷水装置不能覆盖草坪宽度
cnt++;
a[cnt].x = x - sqrt(r * r - h * h / 4.0);
a[cnt].y = x + sqrt(r * r - h * h / 4.0);
}
sort(a + 1, a + 1 + cnt, cmp);
double t = 0;
int ans = 0, bj = 1, i = 1;
while (t < L) {
ans++;
double s = t;
for (; a[i].x <= s && i <= cnt; i++) //依次找能够覆盖L点的最大右端点
if (t < a[i].y)
t = a[i].y;
if (t == s && s < L) {
cout << -1 << endl;
bj = 0;
break;
}
}
if (bj)
cout << ans << endl;
}
return 0;
}
```
## 流水作业调度问题
- 有 $n$ 个作业要在两台机器 $M_1$ 和 $M_2$ 组成的流水线上完成加工。每个作业 $i$ 都必须先花时间 $a_i$ 在 $M_1$ 上加工，然后花时间 $b_i$ 在$M_2$ 上加工
- 确定 $n$ 个作业的加工顺序，使得从作业 $1$ 在机器 $M_1$ 上加工开始到作业 $n$ 在机器 $M_2$ 上加工完为止所用的总时间最短
- 算法：直观上，最优调度一定让 $M_1 , M_2$ 的空闲时间尽量短
- 设 $N_1$ 为 $a<b$ 的作业集合，$N_2$ 为 $a >= b$ 的作业集合，将 $N_1$ 的作业按 $a$ 非减序排序， $N_2$ 中的作业按照 $b$ 非增序排序， 则 $N_1$ 作业接 $N_2$ 作业构成最优排序
- P1248 加工生产调度
- 大胆猜想：要使机器的总时间最短，就要把在 $A$ 机器上加工时间的部件最先加工，这样使得 $B$ 机器能在最短的空闲时间内开始加工
- 把在 $B$ 机器上加工时间最短的部件放在最后加工，这样使得 $A$ 机器用最短时间等待 $B$ 加工完成
- ```c++
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
struct node {
int x, y;
int id;
};
bool cmp1(node a, node b) {
return a.x < b.x;
}
bool cmp2(node a, node b) {
return a.y > b.y;
}
int n, t[N]; // t用来临时存数组的,最后用来存储加工顺序
node a[N], b[N];
int la, lb;
int main() {
cin >> n;
for (int i = 1; i <= n; i++)
cin >> t[i];
for (int i = 1; i <= n; i++) {
int tmp;
cin >> tmp;
if (t[i] < tmp) {
a[++la].x = t[i];
a[la].y = tmp;
a[la].id = i;
} else {
b[++lb].x = t[i];
b[lb].y = tmp;
b[lb].id = i;
}
}
sort(a + 1, a + 1 + la, cmp1);
sort(b + 1, b + 1 + lb, cmp2);
int cnt = 0;
// 计算花费的时间
int ta = 0, tb = 0;
for (int i = 1; i <= la; i++) {
ta += a[i].x;
tb = max(ta, tb) + a[i].y;
t[++cnt] = a[i].id;
}
for (int i = 1; i <= lb; i++) {
ta += b[i].x;
tb = max(ta, tb) + b[i].y;
t[++cnt] = b[i].id;
}
cout << tb << endl;
for (int i = 1; i <= n; i++)
cout << t[i] << " ";
return 0;
}
```
## 带期限和罚款的单位时间任务调度
- 有 $n$ 个任务，每个任务都需要 $1$ 个时间单位执行，任务 $i$ 的截至时间 $d_i(1<=d_i<=n)$ 表示要求任务 $i$ 在时间 $d_i$ 结束时必须完成，误时惩罚 $w_i$ 表示若任务 $i$ 未在时间 $d_i$ 结束之前完成，将导致 $w_i$ 的罚款
- 确定所有任务的执行顺序，使得惩罚最少
- 思路
- 要使得罚款最少，显然应该尽量完成 $w_i$ 值较大的任务
- 按照 $w_i$ 从大到小进行排序，按照排好的顺序依次对人物进行安排
- 安排规则：使处理任务 $i$ 的时间即在 $d[i]$ 之内，又尽量靠后；如果 $d[i]$ 之内的时间都已经排满，就放弃处理此项任务
- 证明
- 假设上述算法不是最优的，那么必然存在某个任务 $j$ 应该安排到处理的过程中但却没有安排。
- 假设我们要将该任务安排进去，由于在时间 $d[i]$ 内都已经排满了，那么就必然需要将一个已安排的任务 $k$ 与之替换，而 $w[k]>=w[j]$ , 这样，替换显然会增加罚款的数额。
- 因此，除上述安排方法以外的安排方法都不会使罚款的数额减少，可知，上述算法得到的结果是最优的
- 实现
- 按照罚款数额从大到小排序
- 顺序处理每个任务，若能安排，则找一个最晚时间；否则放在最后的空位上
- 如果找不到，就不管了
- P1230 智力大冲浪
- ```c++
#include <bits/stdc++.h>
using namespace std;
const int N = 5e2 + 10;
struct node {
int t, w;
bool operator <(node a) {
return w > a.w;
}
};
node a[N];
bool vis[N]; // 标记时间点是否可以用
int m, n;
int main() {
cin >> m >> n;
for (int i = 1; i <= n; i++)
cin >> a[i].t;
for (int i = 1; i <= n; i++)
cin >> a[i].w;
sort(a + 1, a + 1 + n);
for (int i = 1; i <= n; i++) {
bool flg = 1;
for (int j = a[i].t ; j >= 1; j--) {
if (vis[j] == 0) {
vis[j] = 1;
flg = 0;
break;
}
}
if (flg) m -= a[i].w;
}
cout << m;
return 0;
}
```
## 证明：微扰(邻项交换)
- 证明在任意局面下，任何对局部最优策略的微小改变都会造成整体结果变差。经常用以 **"排序"** 为贪心策略的证明
- P1080 国王游戏
- 证明：我们可以假设 $a1*b1 <= a2*b2$
- $1$ 在前的情况 ： $max(1/b1 , a1/b2)$
- $2$ 在前的情况 ： $max(1/b2 , a2/b1)$
- 可以发现当满足 $a1*b1 <= a2*b2$ 的时候，左式 $\leq$ 右式，交换前更优
- 可以发现在任何情况下，减小逆序对数量不会造成整体结果变差，而增加逆序对数量不会使整体结果变好
- 故当逆序对数量为 $0$ 的时候，就是最优策略
- ```c++
// 贪心策略，按照 左手*右手
// 从小到大排序
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
#define int long long
struct node {
int l, r;
};
bool cmp(node a, node b) {
return a.r * a.l < b.r * b.l;
}
// t 来表示左手的乘积
int n, ans, t;
node a[N];
signed main() {
cin >> n;
for (int i = 0 ; i <= n; i++)
cin >> a[i].l >> a[i].r;
// 国王不参与排序
sort( a+1 , a+1+n , cmp);
t = a[0].l; // 左手的乘积
for (int i = 1; i <= n; i++) {
ans = max(ans, t / a[i].r);
t = t * a[i].l;
}
cout << ans;
return 0;
}
```
## 证明： 决策包容性
- 做出局部最优决策后以后，在问题状态空间的可达集合中包含了做出其他任何决策后的可达集合
- 换言之，这个局部最优策略提供的可能性包含了其他所有策略提供的可能性
- P2887 Sunscreen G
- 贪心策略：按照 min SPF递减的顺序把奶牛排序，然后依次在防晒霜里面找 SPF 值最大的使用
- ```c++
证明：
因为奶牛已经按照minSPF 的顺序递减排序，所有每一个不低于当前奶牛
minSPF 值的防晒霜，都不会低于后面其他奶牛的 minSPF
对于当前奶牛可用的任意两瓶防晒霜 x 和 y,如果SPF[X] < SPF[y]
那么后面其他奶牛只可能出现 x,y都能用或者x,y都不能用，或者x能用y不能用，所以 x 的适用范围更广
综上，尽量满足当前的奶牛，并选择 SPF 值尽量大的是最优选择
```
- ```c++
int n, m, ans;
struct node {
int spf, cnt;
};
bool cmp(node a, node b) {
return a.spf > b.spf;
}
struct node1 {
int l, r;
};
bool cmp1(node1 a, node1 b) {
if (a.l != b.l) return a.l > b.l;
return a.r > b.r;
}
node1 a[N];
node b[N];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> a[i].l >> a[i].r;
for (int i = 1; i <= m; i++)
cin >> b[i].spf >> b[i].cnt;
// 按照 minSPF 递减的顺序排序
sort(a + 1, a + 1 + n, cmp1);
// 按照 SPF 递减的顺序排序
sort(b + 1, b + 1 + m, cmp);
// 遍历所有的奶牛
for (int i = 1; i <= n; i++) {
// 遍历所有的防晒霜
for (int j = 1; j <= m; j++) {
if (a[i].l <= b[j].spf && a[i].r >= b[j].spf && b[j].cnt) {
ans++, b[j].cnt--;
break;
}
}
}
cout << ans;
return 0;
}
```
# 反悔贪心
- 思路是无论当前的选项是否最优都接受，然后进行比较，如果选择之后不是最优了，则反悔，舍弃掉这个选项；否则，正式接受，如此往复
- P2949 Work Scheduling G
- ```c++
先假设每一项工作都做，将各项工作按截止时间排序后入队；
在判断第 i 项工作做与不做时，若其截至时间符合条件，
则将其与队中报酬最小的元素比较，若第 i 项工作报酬较高（后悔），
则 ans += a[i].p - q.top()。
用优先队列（小根堆）来维护队首元素最小。
当 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 <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n;
// pair<时间， 收益>
pair<int, int > a[N];
long long ans;
// 存储相反数，最小值
priority_queue<int> q;
int main() {
cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i].first >> a[i].second;
sort(a, a + n);
for (int i = 0; i < n; i++) {
int t = a[i].first;
if (t <= (int)q.size()) { // 当前时间已经被占用了
// 反悔了，有了更好的选择
if (a[i].second > -(q.top())) { // 队列里面最小的没有当前的优秀
ans += a[i].second - (-q.top());
q.pop();
q.push(-a[i].second);
}
} else {
ans += a[i].second;
q.push(-a[i].second);
}
}
cout << ans;
return 0;
}
```
hey_muzili
LV 6
~
2025-11-8 11:33:22 