A2502494904 2023-10-16 16:49 采纳率: 57.1%
浏览 13

有没有简单一点的贪心方法

实验室的一面墙壁被按照长度分割成小面,并被编号成 1,2,…,n,每个部分为一个单位尺寸长并最多挂一个小灯。
每个成员都想在自己的工位边上挂些小灯,并指定了三个号码 b,e,t。这三个数表示该成员想在墙面 b 和 e 之间(包括 b 和 e)挂至少 t 个小灯。

成员们想挂灯带的各自区域可以交叉。你的任务是求出能满足所有要求的最少的小灯的数量。

tips: qsort()会很好用
Input
输入的第一行是一个整数,代表区域的个数 n。

输入的第二行是一个整数,代表成员个数 h。
Output
输出一行一个整数,代表最少的小灯个数。
9
4
1 4 2
4 6 2
8 9 2
3 5 2

  • 写回答

2条回答 默认 最新

  • 面向答案C语言 2023-10-17 02:17
    关注

    在区域有交集的地方尽可能挂多的灯
    只要专注区域无需关注确切的目标 例如 区间a-b的需求是两盏灯 那就记录灯的数量 利用qsort排序 看看区间内灯的数量 然后让结果加上需要安装的灯的数量-区间内原有灯的数量即可

    评论 编辑记录

报告相同问题?

问题事件

  • 创建了问题 10月16日