Lesson 5 - 贪心进阶

Enryh2024年10月25日大约 12 分钟

题目示例

3312 节省时间2

提示

为了最小化总答疑时间，我们需要将答疑时间较短的学生排在前面，这样可以减少后续学生的等待时间。

贪心策略分析

排序：将所有学生的答疑时间从小到大排序。这样，最短的答疑时间会在前面，使得后续学生的等待时间最小化。
计算总时间：
- 初始化总时间为前两个学生的答疑时间之和。
- 从第三个学生开始，当前学生的完成时间应为前面第 $i - 2$ 个学生的完成时间加上自己的答疑时间。第 $i - 1$ 个学生是在另一位老师那里答疑，因此不需要计算他们的等待时间。
- 将当前学生的完成时间加入总时间中。
输出结果：最后输出计算得到的最小总答疑时间。

代码实现

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n; // 输入学生人数
    vector<int> a(n + 1); // 创建数组存储每位同学的答疑时间
    for(int i = 1; i <= n; i++){
        cin >> a[i]; // 输入每位同学的答疑时间
    }
    sort(a.begin() + 1, a.end()); // 从小到大排序
    int sum = a[1] + a[2]; // 初始化总时间为前两位学生的答疑时间
    for(int i = 3; i <= n; i++){
        a[i] += a[i - 2]; // 更新当前学生的完成时间
        sum += a[i]; // 累加总时间
    }
    cout << sum; // 输出最少的总答疑时间
    return 0;
}

3315 节省时间3

提示

为了最小化总答疑时间，我们需要优先处理答疑时间短的学生，并合理分配学生到不同的老师。

贪心策略分析

排序：将所有学生的答疑时间从小到大排序，这样较短的答疑时间会在前面，减少后续学生的等待时间。
分配答疑时间：
- 初始化前 $r$ 位老师的答疑时间。
- 从第 $r + 1$ 位学生开始，当前学生的完成时间应为其答疑时间加上与其分配的老师前 $r$ 位学生的完成时间。通过将学生均匀地分配给老师，可以确保每位老师的负担相对均衡。
计算平均时间：最后计算所有学生的总答疑完成时间，并除以学生人数，输出结果保留两位小数。

代码实现

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n, r;
    cin >> n >> r; // 输入学生与老师的人数
    vector<int> stu(n + 1);
    for(int i = 1; i <= n; i++) cin >> stu[i]; // 输入每位同学的答疑时间
    sort(stu.begin() + 1, stu.end()); // 从小到大排序
    for(int i = r + 1; i <= n; i++) stu[i] += stu[i - r]; // 更新答疑完成时间

    int sum = 0;
    for(int i = 1; i <= n; i++) sum += stu[i]; // 累加总时间
    cout << fixed << setprecision(2); // 设置输出格式
    cout << 1.0 * sum / n; // 输出平均时间
    return 0;
}

7973 区间选点

提示

为了解决这个问题，我们需要选择尽量少的点，使得每个给定的区间都至少包含一个选中的点。采用贪心策略可以有效地达到这个目标。

贪心策略分析

区间排序：首先将所有的区间按右端点进行排序。这样做是为了确保我们能在尽可能靠前的位置选择点，以覆盖后续的更多区间。
选择点：
- 初始化一个变量 cur，用于记录上一个选择的点的位置，初始值设为负无穷。
- 遍历每个区间，对于每个区间的左端点 $l$ 和右端点 $r$ ：
  - 如果当前的 cur 小于区间的左端点 $l$ ，这意味着当前的选择点无法覆盖这个区间，因此需要选择新的点，即当前区间的右端点 $r$ 。
  - 选择点后，更新 cur 为 $r$ ，并增加选点计数。
输出结果：最终输出所选点的最小数量。

代码实现

#include<bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    vector< pair<int, int> > points(n);
    
    // 读取区间
    for (int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;
        points[i] = {r, l};  // 按右端点排序，将右端点放在第一个位置
    }
    
    // 按右端点排序
    sort(points.begin(), points.end());

    int ans = 0;
    int cur = INT_MIN;  // 初始化最后选定的点位置

    // 遍历每个区间
    for (auto p : points) {
        int l = p.second; // 左端点在第二个位置
        int r = p.first;  // 右端点在第一个位置
        
        // 如果当前区间不被 cur 覆盖，则选择 r 作为新的点
        if (cur < l) {
            ans++;
            cur = r;
        }
    }

    // 输出最小选点数量
    cout << ans << endl;

    return 0;
}

1551 导弹攻防战

提示

为了解决导弹拦截问题，我们需要合理使用拦截系统，以确保每一发导弹的高度满足拦截条件。

贪心策略分析

理解问题：我们可以拦截的第一发导弹高度没有限制，但后续导弹必须在前一发导弹的高度之下。因此，我们需要找到一种策略来最小化拦截系统的数量。
遍历导弹高度：
- 使用一个动态数组 dd 来记录当前已使用的拦截系统的最高高度。
- 对于每一个导弹的高度，检查当前的拦截系统是否可以拦截。
- 如果当前导弹高度低于或等于某个拦截系统的最高高度，则更新该系统的高度为当前导弹的高度。
- 如果没有合适的系统可以拦截当前导弹，则新增一个拦截系统。
输出结果：最终，dd 的长度即为所需的最小拦截系统数量。

代码实现

#include<bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;  // 输入导弹数量
    vector<int> heights(n);  // 存储导弹高度
    for (int i = 0; i < n; i++) {
        cin >> heights[i];  // 输入每个导弹的高度
    }

    vector<int> dd;  // 用于记录当前拦截系统的最高高度
    for (int height : heights) {
        bool flag = false;
        int mini;
        for(int i = 0; i < dd.size(); i++){
            if(dd[i] >= height){
                flag = true;
                mini = i;
                break;
            }
        }
        if(flag){
            dd[mini] = height; // 更新该拦截系统的最高高度
        } else {
            dd.push_back(height); // 新增一个拦截系统
        }
    }

    cout << dd.size() << endl;  // 输出所需的拦截系统数量
    return 0;
}

3318 割水稻

提示

为了最小化所有农民的总收获时间，我们需要合理安排镰刀的使用顺序，优先让收割时间较短的农民使用镰刀。

贪心策略分析

排序农民的收割时间：首先，将所有农民的收割时间从小到大排序。这样可以确保在等待时间上尽量减少后续农民的等待时间。
分配收割时间：
- 初始化前 $r$ 位农民的收割时间。
- 从第 $r + 1$ 位农民开始，计算他们的完成时间。每个农民的完成时间等于其自己的收割时间加上之前 $r$ 位农民中每位的完成时间。
- 具体来说，第 $i$ 位农民的收割时间应更新为：f[i] += f[i - r]。
计算总时间：遍历所有农民，将他们的完成时间累加得到总的收获时间。
输出结果：最后输出计算得到的最小总收获时间。

代码实现

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n, r;
    cin >> n >> r; // 输入农民人数和镰刀数量
    vector<int> f(n + 1); // 存储每位农民的收割时间
    for(int i = 1; i <= n; i++) cin >> f[i]; // 输入收割时间
    sort(f.begin() + 1, f.end()); // 从小到大排序
    for(int i = r + 1; i <= n; i++) f[i] += f[i - r]; // 更新每位农民的收割时间
    
    int sum = 0;
    for(int i = 1; i <= n; i++) sum += f[i]; // 累加总收获时间

    cout << sum; // 输出最少的总收获时间
    return 0;
}

1550 糖果问题

提示

为了确保任意两个相邻的糖果盒中糖果的总数不超过 $x$ ，我们需要计算至少需要吃掉多少颗糖果。

贪心策略分析

问题理解：我们有 $N$ 个糖果盒，每个盒子里有一定数量的糖果。目标是确保任意相邻两个盒子的糖果总数不超过 $x$ 。
遍历糖果盒：从第一个糖果盒开始，依次检查每对相邻的盒子：
- 计算当前盒子和下一个盒子的糖果总数。
- 如果总数超过 $x$ ，则需要减少糖果。计算需要吃掉的糖果数量 d = (糖果总数 - x)。
吃糖果的选择：
- 首先尝试从右侧的糖果盒（当前盒子的后一个）中吃掉糖果。如果右侧的盒子能提供足够的糖果，直接减少右侧盒子的糖果数量。
- 如果右侧盒子的糖果不足，则将剩余需要吃掉的糖果从左侧盒子中吃掉。
累加糖果数量：将每次需要吃掉的糖果数量累加到总数中。
输出结果：最终输出总共吃掉的糖果数量。

代码实现

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n, x;
    cin >> n >> x; // 输入糖果盒数量和最大糖果总数
    vector<int> candy(n);
    
    for(int i = 0; i < n; i++) cin >> candy[i]; // 输入每个盒子的糖果数量
    
    int ans = 0; // 初始化需要吃掉的糖果数量
    for(int i = 1; i < candy.size(); i++){
        if(candy[i] + candy[i - 1] > x){ // 如果相邻两个盒子的糖果总数超过 x
            int d = candy[i] + candy[i - 1] - x; // 计算需要吃掉的糖果数量
            ans += d; // 增加到总数
            if(candy[i] >= d) candy[i] -= d; // 尝试从右侧盒子吃糖果
            else{
                d -= candy[i]; // 如果右侧盒子不够，则从左侧盒子吃
                candy[i] = 0; // 右侧盒子吃光
                candy[i - 1] -= d; // 从左侧盒子吃剩下的糖果
            }
        }
    }
    cout << ans; // 输出至少要吃掉的糖果数量
    return 0;
}

1779 区间合并

提示

通过合并相邻或相交的区间，我们可以判断所有区间是否可以最终合并为一个闭区间，并输出合并后的区间的左右边界。

贪心策略分析

区间表示：每个区间表示为 $[a_{i}, b_{i}]$ ，我们需要处理 $n$ 个这样的区间。
排序：首先，将所有区间按照左端点 $a_{i}$ 进行排序。这样可以方便我们按顺序检查区间是否可以合并。
合并过程：
- 初始化合并后的左边界 $L$ 和右边界 $R$ 分别为第一个区间的左端点和右端点。
- 遍历每个区间，对于当前区间 $[l, r]$ ：
  - 如果当前的右边界 $R$ 小于当前区间的左端点 $l$ ，这表示当前区间与之前的区间不相交或相邻，因此不能合并，输出 "no"。
  - 否则，更新右边界 $R$ 为当前区间的右端点 $r$ 和之前的 $R$ 中的较大值。
输出结果：遍历结束后，如果所有区间都能合并，输出最终的左边界和右边界。

代码实现

#include<bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n; // 输入区间数量
    
    vector< pair<int, int> > points(n);
    
    // 读取区间
    for (int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;
        points[i] = {l, r}; // 存储区间
    }
    
    // 按左端点排序
    sort(points.begin(), points.end());

    int L = points[0].first, R = points[0].second; // 初始化合并后的区间

    // 遍历每个区间
    for (int i = 1; i < points.size(); i++) {
        int l = points[i].first; // 当前区间左端点
        int r = points[i].second; // 当前区间右端点
        
        // 如果当前区间与合并的区间不相交
        if (R < l) {
            cout << "no"; // 输出 no
            return 0;
        } else {
            R = max(r, R); // 更新右边界
        }
    }

    // 输出合并后的区间
    cout << L << ' ' << R;
    return 0;
}

1473 绿化方案

提示

为了满足居民的绿化建议，我们需要在指定的路段种树，最终目标是最小化所种树的数量。

贪心策略分析

问题建模：每条路段可以种一棵树，居民提出的建议形成了多个区间，每个区间需要种植一定数量的树。
输入处理：我们首先读取路段的数量 $n$ 和建议的数量 $h$ ，然后读取每个建议，存储为区间形式 $[b, e]$ 以及需要的树的数量 $t$ 。
贪心策略：
- 将所有的建议按左端点 $b$ 降序排序，这样可以优先处理左端点较大的区间。
- 对于每个建议，我们检查其区间内已经种植的树的数量，如果不足，则需要在该区间内种植缺少的树。
- 在种树时，我们从区间的左端点开始种树，直到满足建议中要求的树的数量。
结果计算：最后统计所有种植的树的数量，输出结果。

代码实现

#include<bits/stdc++.h>
using namespace std;

struct node {
    int b, e, t; // 区间的左端点、右端点和需要的树的数量
} a[5001];

bool cmp(node x, node y) {
    return x.b > y.b; // 左端点降序排序
}

int tree[30001]; // 记录每个路段是否种树，0表示未种树

int main() {
    int n, h;
    cin >> n >> h; // 输入路段数和建议数
    for (int i = 1; i <= h; i++) {
        cin >> a[i].b >> a[i].e >> a[i].t; // 输入每个建议
    }
    sort(a + 1, a + 1 + h, cmp); // 按左端点降序排序

    for (int i = 1; i <= h; i++) { // 遍历每个建议
        int cnt = 0; // 记录当前区间内已经种的树
        for (int j = a[i].b; j <= a[i].e; j++) { // 统计当前区间内的树
            if (tree[j] == 1) {
                cnt++;
            }
        }
        if (cnt >= a[i].t) continue; // 已满足条件，无需种树
        else cnt = a[i].t - cnt; // 计算需要种植的数量
        
        for (int j = a[i].b; j <= a[i].e; j++) { // 从左到右种树
            if (tree[j] == 0) {
                tree[j] = 1; // 种树
                cnt--;
            }
            if (cnt == 0) break; // 种植完成
        }
    }

    int ans = 0; // 统计最终种植的树的数量
    for (int i = 1; i <= n; i++) {
        if (tree[i] == 1) ans++; // 统计已种树的路段
    }
    
    cout << ans; // 输出结果
    return 0;
}