NEFU-2023-算法设计与分析实验三贪心算法设计

野性酷女 2024-04-17 11:43 75阅读 0赞

## 作者的话 ##

**大底包含了算法硬性规定的作业代码，并非最优解，仅供参考并会持续更新。勿要无脑copy，对自己负责。如果代码有误或者优化建议，直接相应博客下方评论或者qq找我如果对代码有理解不了的或者疑惑可以询问我，但是请确保你已经自己思考过或者查过搜索引擎（如果我原模原样搜到了资料的话我会锤你的hh）。一些语法和库的资料查询网站受个人风格影响，部分题目解题方式可能没按照教学要求，如有必要请自己按教学要求做一遍。如果可以的话，麻烦借鉴完以后给我博客来个三连啥的，这可能对我以后找工作或者其他博客的推广什么的有些帮助，感谢**

**如要系统学习可看我的另一篇博客[算法小课堂（五）贪心算法][Link 1]**

## 题目一：**最优服务次序问题** ##

> （1）问题描述：
> 
> 　　设有n 个顾客同时等待一项服务。顾客i需要的服务时间为ti, 1<=i <= n 。应如何安排n个顾客的服务次序才能使平均等待时间达到最小?平均等待时间是n 个顾客等待服务时间的总和除以n。
> 
> （2）编程任务：
> 
> 　　对于给定的n个顾客需要的服务时间，编程计算最优服务次序。
> 
> （3）数据输入：
> 
> 　　第一行是正整数n，表示有n 个顾客。接下来的1行中，有n个正整数，表示n个顾客需要的服务时间。
> 
> （4）结果输出:
> 
> 　　计算出的最小平均等待时间。
> 
> （5）输入示例
> 
> 10
> 
> 56 12 1 99 1000 234 33 55 99 812
> 
> （6）输出示例

#include <stdio.h>
    #include <stdlib.h>
    #include <algorithm>
    using namespace std;
    
    const int MAXN = 1000;
    int n;
    int t[MAXN];
    
    // 比较函数，用于sort函数排序
    bool cmp(int a, int b) {
        return a < b;
    }
    
    int main() {
        // 输入顾客数量
        scanf("%d", &n);
        // 输入每个顾客需要的服务时间
        for (int i = 0; i < n; i++) {
            scanf("%d", &t[i]);
        }
        // 排序
        sort(t, t + n, cmp);
        double ans = 0;
        // 计算平均等待时间
        for (int i = 0; i < n; i++) {
            ans += (n - i) * t[i];
        }
        printf("%.2lf\n", ans / n);
        return 0;
    }

## **题目二区间相交问题** ##

> （1）问题描述：
> 
> 　　给定x 轴上n 个闭区间。去掉尽可能少的闭区间，使剩下的闭区间都不相交。
> 
> （2）编程任务：
> 
> 　　给定n 个闭区间，编程计算去掉的最少闭区间数。
> 
> （3）数据输入：
> 
> 　　第一行是正整数n，表示闭区间数。接下来的n行中，每行有2 个整数，分别表示闭区间的2个端点。
> 
> （4）结果输出:
> 
> 计算出的去掉的最少闭区间数。
> 
> （5）输入示例
> 
> 3
> 
> 10 20
> 
> 10 15
> 
> 20 15
> 
> （6）输出文件示例
> 
> 2

#include <iostream>
    
    #include <algorithm>
    
    using namespace std;
    
     
    
    const int N = 1010;
    
     
    
    struct Range {
    
        int l, r;
    
        bool operator< (const Range& W) const {
    
            return r < W.r;
    
        }
    
    }range[N];
    
     
    
    int main() {
    
        int n;
    
        cin >> n; // 输入闭区间数
    
        for (int i = 0; i < n; i++) {
    
            cin >> range[i].l >> range[i].r; // 输入每个闭区间的左右端点
    
        }
    
        sort(range, range + n); // 按照区间右端点从小到大排序
    
        int res = 1, right = range[0].r; // res表示去掉的区间数，right表示当前区间右端点的最小值
    
        for (int i = 1; i < n; i++) {
    
            if (range[i].l > right) { // 如果当前区间和前面的区间没有重叠部分
    
                res++; // 就保留这个区间
    
                right = range[i].r;
    
            }
    
        }
    
        cout << n-res << endl; // 输出去掉的最少闭区间数
    
        return 0;
    
    }

## 题目三**汽车加油问题** ##

> 问题描述：一辆汽车加满油后可行驶nkm。旅途中有若干加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。
> 
> 算法设计：对于给定的n和k个加油站位置，计算最少加油次数。
> 
> 数据输入：n：表示汽车加满油后可行驶nkm
> 
> k：旅途中有k个加油站
> 
> k+1个整数：表示第k个加油站与第k-1个加油站之间的距离。第0个加油站表示出发地，汽车已加满油。第k+1个加油站表示目的地。
> 
> 数据输出：最少加油次数和具体在哪几个加油站加油。
> 
> 例如： n=7 k=7
> 
> K+1个整数：1 2 3 4 5 1 6 6
> 
> 最优值：4

#include <iostream>
    #include <algorithm>
    using namespace std;
    
    const int N = 1010;
    
    int n, k;
    int d[N];
    
    int main() {
        cin >> n >> k;
        for (int i = 1; i <= k + 1; i++) {
            cin >> d[i];
        }
        int res = 1, now = n;
        for (int i = 1; i <= k; i++) {
            if (now < d[i]) { // 如果当前油量无法到达下一个加油站
                res++; // 就在当前加油站加满油
                now = n; // 油量变为n
            }
            now -= d[i]; // 消耗d[i]的油量
        }
        cout << res << endl; // 输出最少加油次数
        return 0;
    }

[Link 1]: https://blog.csdn.net/qq_62377885/article/details/130042998