C++新U4-贪心算法2

[【贪心算法(二)】分发饼干]

【题意分析】
将饼干分发孩子手上，并且使得满足的孩子数量最多

【思路分析】
为了尽可能满足最多数量的孩子，按照孩子想要获得的饼干大小从小到大的顺序依次满足每个孩子，且对于每个孩子，应该选择可以满足这个孩子的胃口且尺寸最小的饼干。将饼干大小和孩子所需的饼干大小从小到大排序，都从第一个开始选取，如果可以满足当前孩子需求，满足数量+1，并且孩子和饼干都后移一位，如果不满足那么就将饼干后移一位，查看更加大的饼干是否可以满足当前的孩子，直到饼干或者孩子遍历完

【参考代码】
#include <algorithm>
#include <iostream>
using namespace std;
//g为饼干的大小，c孩子所需的饼干大小
int g[10010], c[10010];
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> g[i];
    }
    for (int i = 0; i < m; i++) {
        cin >> c[i];
    }
    //将饼干大小和孩子所需的饼干大小从小到大排序
    sort(g, g + n);
    sort(c, c + m);
    // 记录当前有多少个孩子满足
    int ans = 0;
    // 分别表示饼干和孩子的下标
    int i = 0, j = 0;
    while (i < n && j < m) {
        // 当前的饼干大小可以满足下标为j的孩子
        if (g[i] >= c[j]) {
            // 将人和饼干往后移动一位，满足的人数+1
            i++;
            j++;
            ans++;
        } else {
            i++;
        }
    }
    // 输出满足的人数
    cout << ans << endl;
    return 0;
}

View Code

[【贪心算法(二)】游玩]

【题意分析】
让所有人都能坐船出海游玩，尽可能让两个人坐一条船，使得出海的船数量最少

【思路分析】
要使得出海的船数量最少，尽可能让两人去搭载一艘船。考虑体重最轻的人，若他不能与体重最重的人同乘一艘船，那么体重最重的人无法与任何人同乘一艘船，此时应单独分配一艘船给体重最重的人。若他能与体重最重的人同乘一艘船，那么他也能与其余任何人同乘一艘船，为了尽可能地利用船的承载重量，让他与体重最重的人同乘一艘船。

【参考代码】
#include <algorithm>
#include <iostream>
using namespace std;
int arr[1010];
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    // 按照体重从轻到重排序
    sort(arr, arr + n);
    // 建立双指针，一个指针从头选择重量小的人，另一个从尾选择重量大的人
    int i = 0;
    int j = n - 1;
    // 统计需要多少条船
    int ans = 0;
    while (i <= j) {
        // 当前体重最轻的人和体重最重的人并未超出船的上限
        if (arr[i] + arr[j] <= m) {
            i++;
            j--;
        }
        // 超出船的上限，体重重的人一个人坐船
        else {
            j--;
        }
        // 船的数量+1
        ans++;
    }
    cout << ans << endl;
    return 0;
}

View Code

[【贪心算法(二)】活动安排]

 重点：结束时间早意味着可以给后面留出更多的时间安排活动

【题意分析】
选取尽可能的多的活动，并且选取的活动的时间并不冲突。

【思路分析】
为了参加更多的活动，对于每一个活动越早结束，其他活动越可能发生。使用贪心算法来解决这个问题。首先将活动按照结束时间从小到大进行排序，然后依次选择结束时间最早的活动判断是否能加入到最大集合中并进行相应的计数

首选左端点最小的活动，接下来判断后面的每一个活动看看是否与上一个活动冲突(即当前的左端点<=上一个选择的活动的右端点)，不冲突选择该区间，计数++，更新上一个右端点的变量。

【参考代码】
#include <algorithm>
#include <iostream>
using namespace std;
// 定义结构体，参数为开始时间和结束时间
struct node {
    int s, e;
} a[1010];
// 排序，将结束时间早的排序在前面
bool cmp(node a, node b) {
    return a.e < b.e;
}
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i].s >> a[i].e;
    }
    sort(a, a + n, cmp);
    // 定义变量为活动结束时间，以第一个数结尾作为活动结束时间
    int last = a[0].e;
    // 活动的参加数量
    int num = 1;
    for (int i = 1; i < n; i++) {
        // 当前活动的开始时间是大于等于活动结束时间
        if (a[i].s >= last) {
            // 活动选取数量+1,更新活动结束时间
            num++;
            last = a[i].e;
        }
    }
    // 输出活动的参加数量
    cout << num;
    return 0;
}

View Code

作业：系统中有讲解