算法提高篇基础算法第一章 - 贪心算法
1422：【例题1】活动安排
这是一个经典的活动选择问题，可以使用贪心算法来解决。我们可以按照活动的结束时间对活动进行排序，然后从最早结束的活动开始选择，不断更新当前可选活动的起始时间，直到所有活动都被考虑过。
下面是使用C++实现的解答：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;// 定义活动结构体
struct Activity {int start;int end;
};// 按照活动结束时间排序
bool cmp(Activity a, Activity b) {return a.end < b.end;
}int main() {int n;cin >> n;vector<Activity> activities(n);for (int i = 0; i < n; i++) {cin >> activities[i].start >> activities[i].end;}// 按照活动结束时间排序sort(activities.begin(), activities.end(), cmp);int count = 1; // 选择的活动数量，至少可以选择第一个活动int lastEnd = activities[0].end; // 上一个选择的活动的结束时间for (int i = 1; i < n; i++) {if (activities[i].start >= lastEnd) {count++;lastEnd = activities[i].end;}}cout << count << endl;return 0;
}
解释：
-
我们首先定义了一个
Activity结构体，包含活动的起始时间start和结束时间end。 -
然后定义了一个比较函数
cmp，用于按照活动的结束时间对活动进行排序。 -
在主函数中，我们读取活动的数量
n，然后读取每个活动的起始时间和结束时间，并存储到activities向量中。 -
接下来，我们使用
sort函数对activities向量进行排序，按照活动的结束时间从小到大排序。 -
我们初始化
count变量为1，表示至少可以选择第一个活动，同时将lastEnd变量初始化为第一个活动的结束时间。 -
然后，我们从第二个活动开始遍历
activities向量，对于每个活动，如果它的起始时间大于等于lastEnd，说明它与上一个选择的活动不冲突，可以选择该活动，并更新count和lastEnd变量。 -
最后，我们输出选择的活动数量
count。
该解答的时间复杂度为O(nlogn)，主要是由于排序操作。空间复杂度为O(n)，用于存储活动的向量。
1423：【例题2】种树
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;struct tree{int B;int E;int T;
};bool cmp(tree a, tree b){return a.E < b.E;
}int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n, m, ans = 0;cin >> n >> m;vector<tree> a(m + 1);for (int i = 1; i <= m; i++){cin >> a[i].B >> a[i].E >> a[i].T; }sort(a.begin(), a.end(), cmp);vector<bool> f(n, false);for (int i = 1; i <= m; i++){int k = 0;for (int j = a[i].B; j <= a[i].E; j++){if (f[j]) k++;}if (k >= a[i].T) {continue;} else {for (int l = a[i].E; l >= a[i].B; l--){if (!f[l]) {k++;f[l] = true;if (k >= a[i].T) break;}}}}for (int i = 1; i <= n; i++){if (f[i]) ans++;}cout << ans << endl;return 0;
}
1424：【例题3】喷水装置
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;// 喷头结构
struct Sprinkler {double left, right; // 喷头覆盖的左右端点
};// 按照左端点排序喷头
bool compareSprinkler(const Sprinkler &a, const Sprinkler &b) {return a.left < b.left;
}int main() {int T; // 测试数据组数cin >> T;while (T--) {int n, L, W;cin >> n >> L >> W;vector<Sprinkler> sprinklers;for (int i = 0; i < n; ++i) {int position, radius;cin >> position >> radius;double width = (double)W / 2;// 计算喷头能覆盖的最左和最右的位置if (radius > width) {double reach = sqrt(radius*radius - width*width);sprinklers.push_back({(double)position - reach, (double)position + reach});}}// 按左端点排序sort(sprinklers.begin(), sprinklers.end(), compareSprinkler);double covered = 0; // 已覆盖的长度int count = 0; // 需要的喷头数量int i = 0; // 当前遍历到的喷头索引bool failed = false; // 是否失败while (covered < L) {double maxCover = covered;// 寻找能覆盖当前未被浇灌区域最远的喷头while (i < n && sprinklers[i].left <= covered) {maxCover = max(maxCover, sprinklers[i].right);i++;}if (maxCover <= covered) { // 如果没有进展，则表示无法继续覆盖failed = true;break;}// 更新已覆盖的区域和喷头计数covered = maxCover;count++;}if (failed) {cout << -1 << endl; // 如果无法覆盖整个草坪，则输出-1} else {cout << count << endl; // 否则，输出需要的最少喷头数量}}return 0;
}