活动选择问题(贪心法)

目录

问题概述

实例分析

代码实现


问题概述

实例分析

求解蓄栏保留问题。农场有n头牛,每头牛会有一个特定的时间区间[b,e]在蓄栏里挤牛奶,并且一个蓄栏里任何时刻只能有一头牛挤奶。现在农场主希望知道最少蓄栏能够满足上述要求,并给出每头牛被安排的方案。对于多种可行方案,输出一种即可。

解:牛的编号为1~n,每头牛的挤奶时间相当于一个活动,与前面活动安排问题不同,前面的活动时间是半闭区间,而这里的活动时间是闭区间,例如这里[2,4]与[4,7]是交叉的,它们不是兼容活动。

采用与求解活动安排问题类似的贪心思路,将所有活动这样排序:

结束时间相同按开始时间递增排序,否则按结束时间递增排序。求出一个最大兼容活动子集,将它们安排在一个蓄栏中(蓄栏编号为1);如果没有安排完,再在剩余的活动再求下一个最大兼容活动子集,将它们安排在另一个蓄栏中(蓄栏编号为2),以此类推。也就是说,最大兼容活动子集的个数就是最少蓄栏个数。

代码实现

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAX = 6;

struct Cow {
    int no;
    int b;
    int e;

    bool operator<(const Cow &s) const {
        if (e == s.e)
            return b <= s.b;
        else
            return e <= s.e;
    }
};

Cow A[MAX] = {{0},{1,1,10},{2,2,4},{3,3,6},{4,5,8},{5,4,7}};

int ans[MAX];

void solve() {
    sort(A + 1, A + MAX);
    memset(ans, 0, sizeof(ans));
    int num = 1;
    for (int i = 1; i <= MAX; i++) {
        if (ans[i] == 0) {
            ans[i] = num;
            int preend = A[i].e;
            for (int j = i + 1; j <= MAX; j++) {
                if (A[j].b > preend && ans[j] == 0) {
                    ans[j] = num;
                    preend = A[j].e;
                }
            }
            num++;
        }
    }
}

int main() {
    solve();
    cout << "ret" << endl;
    for (int i=1; i<=MAX; i++){
        printf("Cow%d: %d\n", A[i].no, ans[i]);
    }
    return 0;
}

代码结果:

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/665449.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

情感读本期刊万方收录综合期刊投稿

《情感读本》杂志是由国家新闻出版总署批准&#xff0c;湖北省新闻出版广电局主管&#xff0c;湖北省期刊协会主办的正规综合类期刊。《情感读本》是一本以推动和发展情感教育、素质教育、人文教育为己任&#xff0c;奉行“立足教育&#xff0c;服务社会”的办刊宗旨&#xff0…

ChatGPT产品创意,直接出概念图

直接问&#xff0c;“给我一个创意点子” AI7号 它推荐我做一个智能家居植物管理系统&#xff0c;嗯&#xff0c;很小众的样子。直接让它出一张概念图吧。 像模像样&#xff0c;一张图太单薄了&#xff0c;再来5张。 呃...做了4张&#xff0c;下面还有每张图的说明。 你觉得怎…

(奇幻森林)POLYGON - Enchanted Forest - Nature Biomes - 3D Environment Art by Synty

各种雄伟的树木,装饰着优雅简化的树叶,在头顶形成了一个天堂般的树冠,在苔藓覆盖的森林地面上投下了宁静的咒语。 每一项资产,从引人入胜的环境材料到平缓的波浪状山丘,都经过精心制作,将您带到魔法和自然融合的地方。POLYGON-魔法森林-自然生物技术为数字领域注入真正魔…

实战16:基于apriori关联挖掘FP-growth算法挖掘关联规则的手机销售分析-代码+数据

直接看视频演示: 基于apriori关联挖掘关联规则的手机销售分析与优化策略 直接看结果: 这是数据展示: 挖掘结果展示: 数据分析展示:

矩阵短视频:成都科成博通文化传媒公司

重塑内容生态与传播格局、在数字化时代&#xff0c;短视频以其独特的形式和高效的传播能力&#xff0c;迅速崛起并成为了社交媒体领域的明星。成都科成博通文化传媒公司​而“矩阵短视频”作为短视频领域的一种新兴策略&#xff0c;正以其独特的优势&#xff0c;逐渐重塑内容生…

【JAVASE】String 类常用方法

1、字符串构造 String类提供的构造方式很多&#xff0c;常用的有三种。 &#xff08;1&#xff09;使用常量串构造 例如&#xff1a; &#xff08;2&#xff09;直接new String对象 例如&#xff1a; &#xff08;3&#xff09;使用字符数组进行构造 例如&#xff1a; 2…

20240531在飞凌的OK3588-C开发板上跑原厂的Buildroot测试ETH0接口【仅供参考】

20240531在飞凌的OK3588-C开发板上跑原厂的Buildroot测试ETH0接口 2024/5/31 20:28 rootrk3588-buildroot:/# ifconfig eth0 up rootrk3588-buildroot:/# ifconfig eth1 up rootrk3588-buildroot:/# ifconfig rootrk3588-buildroot:/# rootrk3588-buildroot:/# ifconfig eth1…

Linux CFS调度器之周期性调度器scheduler_tick函数

文章目录 前言一、简介二、源码分析2.1 scheduler_tick2.2 task_tick2.3 entity_tick2.4 check_preempt_tick2.5 resched_curr 参考资料 前言 Linux内核调度器主要是主调度器和周期性调度器&#xff0c;主调度器请参考&#xff1a;Linux 进程调度之schdule主调度器 一、简介 …

如何在IDEA中实现类似Linux命令那样的外部传参

【背景说明】 IDEA中执行一个程序时&#xff0c;如何就在程序一开始执行给传入你给的参数呢&#xff1f; 【说明】 public static void main(String[] args) throws Exception {} 说明&#xff1a;其实java中main方法里的args这个参数&#xff0c;就是用于接收外部传参的。…

C# 写一个简单的Windows Service的服务程序

项目创建及设定部分 使用VS2019创建项目&#xff0c;选择C# Service的选项 按照你喜欢的方式命名&#xff0c;我这边就默认了 添加安装服务&#xff0c;在Service1.cs[Design]中 在设计界面右击&#xff0c;选择如下的"Add Installer" 在出现的"ProjectInstall…

Ubuntu server 24 (Linux) Snort3 3.2.1.0 Guardian IPtables 联动实战 主动防御系统(ids+ips)

一 Snort3 安装配置&#xff0c;参考:Ubuntu server 24 安装配置 snort3 3.2.1.0 网络入侵检测防御系统 配置注册规则集-CSDN博客 二 安装主动防御程序Guardian 1 下载&#xff0c;解压 tar zxvf guardian-1.7.tar.gz cd guardian-1.7/ 2 配置 #拷贝文件 sudo cp guard…

如何从浅入深理解transformer?

前言 在人工智能的浩瀚海洋中&#xff0c;大模型目前无疑是其中一颗璀璨的明星。从简单的图像识别到复杂的自然语言处理&#xff0c;大模型在各个领域都取得了令人瞩目的成就。而在这其中&#xff0c;Transformer模型更是成为大模型技术的核心。 一、大模型的行业发展现状如…

docker删除所有容器

笔记 要使用 Docker 删除所有容器&#xff08;无论是停止的还是正在运行的&#xff09;&#xff0c;可以按照以下步骤操作&#xff1a; 1. **删除所有正在运行的容器**&#xff1a; 首先&#xff0c;您需要停止所有正在运行的容器。可以使用以下命令&#xff1a; dock…

官方正版 | FastCopy - Windows 上最快的文件复制&备份软件

『FastCopy 软件概述』 FastCopy 是一款高性能的文件复制和备份工具&#xff0c;专为 Windows 操作系统设计。它以其卓越的速度和丰富的功能&#xff0c;在用户中赢得了良好的声誉。以下是 FastCopy 的主要特点和优势&#xff1a; 速度优化&#xff1a;FastCopy 通过多线程、异…

c# - 运算符 << 不能应用于 long 和 long 类型的操作数

Compiler Error CS0019 c# - 运算符 << 不能应用于 long 和 long 类型的操作数 处理方法 特此记录 anlog 2024年5月30日

Day10:平面转换、渐变色

目标&#xff1a;使用位移、缩放、旋转、渐变效果丰富网页元素的呈现方式。 一、平面转换 1、简介 作用&#xff1a;为元素添加动态效果&#xff0c;一般与过渡配合使用。 概念&#xff1a;改变盒子在平面内的形态&#xff08;位移、旋转、缩放、倾斜&#xff09;。 平面转换…

工业安全智勇较量,赛宁网安工业靶场决胜工业网络攻防对抗新战场

2024年1月30日&#xff0c;工信部发布《工业控制系统网络安全防护指南》&#xff08;工信部网安〔2024〕14号&#xff09;&#xff0c;围绕安全管理、技术防护、安全运营、责任落实四方面提出安全防护要求&#xff0c;强调聚焦安全薄弱关键环节&#xff0c;强化技术应对策略&am…

说说你对单例模式的理解?如何实现?

一、是什么 单例模式&#xff08;Singleton Pattern&#xff09;&#xff1a;创建型模式&#xff0c;提供了一种创建对象的最佳方式&#xff0c;这种模式涉及到一个单一的类&#xff0c;该类负责创建自己的对象&#xff0c;同时确保只有单个对象被创建 在应用程序运行期间&am…

代码随想录算法训练营第四十四天|01 背包、动态规划:01背包理论基础(滚动数组)、416. 分割等和子集

01 背包 文档讲解&#xff1a;代码随想录 题目链接&#xff1a;46. 携带研究材料&#xff08;第六期模拟笔试&#xff09; 有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]&#xff0c;得到的价值是value[i] 。每件物品只能用一次&#xff0c;求解将哪些物…

Day-04python模块

一、模块 1-1 Python 自带模块 Json模块 处理json数据 {"key":"value"} json不是字典 本质是一个有引号的字符串数据 json注意点 {} 中的数据是字符串引号必须是双引号 使用json模块可以实现将json转为字典&#xff0c;使用字典的方法操作数据 。 或者将…