算法提高篇基础算法第一章 - 贪心算法

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;
}

解释：

1. 我们首先定义了一个Activity结构体，包含活动的起始时间start和结束时间end。

2. 然后定义了一个比较函数cmp，用于按照活动的结束时间对活动进行排序。

3. 在主函数中，我们读取活动的数量n，然后读取每个活动的起始时间和结束时间，并存储到activities向量中。

4. 接下来，我们使用sort函数对activities向量进行排序，按照活动的结束时间从小到大排序。

5. 我们初始化count变量为1，表示至少可以选择第一个活动，同时将lastEnd变量初始化为第一个活动的结束时间。

6. 然后，我们从第二个活动开始遍历activities向量，对于每个活动，如果它的起始时间大于等于lastEnd，说明它与上一个选择的活动不冲突，可以选择该活动，并更新count和lastEnd变量。

7. 最后，我们输出选择的活动数量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;
}