欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！
专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。
适合人群：
- 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
- 希望系统学习C++/Python编程的初学者
- 想要提升算法与编程能力的编程爱好者
附上汇总贴：USACO历年白银组真题解析 | 汇总-CSDN博客
P11453 Deforestation
【题目来源】
洛谷：[P11453 USACO24DEC] Deforestation S - 洛谷
【题目描述】
Farmer John 正在扩大他的农场！他已经找到了完美的位置——红黑森林，由数轴上的 \(N\) 棵树（\(1≤N≤10^5\)）组成，第 \(i\) 棵树位于位置 \(x_i\)（\(−10^9≤x_i≤10^9\)）。
环境保护法限制了 Farmer John 可以砍伐哪些树来为他的农场腾出空间。有 \(K\) 个限制（\(1≤K≤10^5\)），规定在线段 \([l_i,r_i]\)（包含端点）中必须始终至少存在 \(t_i\) 棵树（\(−10^9≤l_i,r_i≤10^9\)）。输入保证红黑森林初始时满足这些限制。
Farmer John 想要他的农场尽可能大。请帮助他计算他可以砍伐的树的最大数量，同时仍然满足所有限制！
【输入】
每个测试点包含 \(T\)（\(1≤T≤10\)）个独立的测试用例。输入保证一个测试点中的所有 \(N\) 之和以及 \(K\) 之和均不超过 \(3⋅10^5\)。
输入的第一行包含 \(T\)。每个测试用例的格式如下：
- 第一行包含整数 \(N\) 和 \(K\)。
- 下一行包含 \(N\) 个整数 \(x_1,\cdots,x_N\)。
- 以下 \(K\) 行，每行包含三个空格分隔的整数 \(l_i\)，\(r_i\) 和 \(t_i\)。
【输出】
对于每个测试用例，输出一行，包含一个整数，表示 Farmer John 可以砍伐的树的最大数量。
【输入样例】
3
7 1
8 4 10 1 2 6 7
2 9 3
7 2
8 4 10 1 2 6 7
2 9 3
1 10 1
7 2
8 4 10 1 2 6 7
2 9 3
1 10 4
【输出样例】
4
4
3
【算法标签】
《洛谷 P11453 Deforestation》 #贪心# #线段树# #二分# #堆# #差分约束# #USACO# #2024#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 100005, M = N * 3; // 最大顶点数和边数
int T, n, k; // T: 测试用例数, n: 点数, k: 区间约束数
int x[N]; // 点坐标数组
int h[N], e[M], ne[M], w[M], idx; // 链式前向星存储图
int dist[N]; // 最长距离数组
bool st[N]; // 标记顶点是否在队列中/*** 添加有向边* @param a 起点* @param b 终点* @param c 权重*/
void add(int a, int b, int c)
{e[idx] = b; // 边指向的顶点w[idx] = c; // 边的权重ne[idx] = h[a]; // 指向原链表头h[a] = idx++; // 更新头指针
}/*** SPFA算法求最长路径* 从顶点0开始，计算到所有顶点的最长路径*/
void spfa()
{// 初始化距离为负无穷memset(dist, -0x3f, sizeof(dist));memset(st, 0, sizeof(st));queue<int> q; // SPFA队列q.push(0); // 起点入队st[0] = true; // 标记在队列中dist[0] = 0; // 起点距离为0while (!q.empty()){int t = q.front(); // 取出队首q.pop();st[t] = false; // 标记不在队列中// 遍历t的所有邻接边for (int i = h[t]; i != -1; i = ne[i]){int j = e[i]; // 邻接顶点// 松弛操作：求最长路径if (dist[j] < dist[t] + w[i]){dist[j] = dist[t] + w[i]; // 更新最长距离// 如果j不在队列中，入队if (!st[j]){q.push(j);st[j] = true;}}}}
}int main()
{// 输入测试用例数cin >> T;while (T--){// 输入点数和区间约束数cin >> n >> k;// 初始化邻接表memset(h, -1, sizeof(h));idx = 0;// 输入n个点的坐标for (int i = 1; i <= n; i++){cin >> x[i];}// 对点坐标排序sort(x + 1, x + n + 1);// 添加基础约束边// 顶点编号0~n，表示排序后的前缀for (int i = 1; i <= n; i++){// 约束1: S_i - S_{i-1} ≤ 1// 即: S_{i-1} - S_i ≥ -1// 建边: i → i-1，权重-1add(i, i - 1, -1);// 约束2: S_i ≥ S_{i-1}// 即: S_i - S_{i-1} ≥ 0// 建边: i-1 → i，权重0add(i - 1, i, 0);}// 处理k个区间约束while (k--){int l, r, t;cin >> l >> r >> t;int len = r - l + 1; // 区间长度（未使用）// 在排序后的点数组中查找l和r对应的位置// lower_bound: 找到第一个≥l的点l = lower_bound(x + 1, x + n + 1, l) - x;// upper_bound: 找到第一个>r的点，然后-1得到最后一个≤r的点r = upper_bound(x + 1, x + n + 1, r) - x - 1;// 添加区间约束边// 如果l≤r，表示有满足条件的点// 约束: S_r - S_{l-1} ≥ t// 建边: l-1 → r，权重tadd(l - 1, r, t);}// 执行SPFA算法求最长路径spfa();/*** 输出结果* 设S_i表示前i个点中被选中的点数* 我们求的是S_n的最大值* 但题目要求的是不被选中的点数* 所以结果为: n - S_n*/cout << n - dist[n] << endl;}return 0;
}
【运行结果】
3
7 1
8 4 10 1 2 6 7
2 9 3
4
7 2
8 4 10 1 2 6 7
2 9 3
1 10 1
4
7 2
8 4 10 1 2 6 7
2 9 3
1 10 4
3