当前位置: 首页 > news >正文

贪心算法

 int a[1000], b=5, c=8;
 swap(b, c);    // 交换操作
 memset(a, 0, sizeof(a)); // 初始化为0或-1

引导问题

为一个小老鼠准备了M磅的猫粮,准备去和看守仓库的猫做交易,因为仓库里有小老鼠喜欢吃的五香豆,第i个房间有J[i] 磅的五香豆,并且需要用F[i]磅的猫粮去交换;求老鼠最多可换多少豆?若五香豆不能全换猫粮,按比例换。

Sample Input 
  5 3 ——M猫粮   N房间
  7 2 ——五香豆  猫粮
  4 3
  5 2
  -1 -1 —— 结束

Sample Output
  13.333

由按比例换,7/2=3.5  4/3=1.333...  5/2=2.5  3.5最大 排序,一次换——7+5+1.3333=13.333


初识贪心

在对问题求解时,总是做出在当前看来是最好的选择

也就是说,不从整体上加以考虑,所作出的仅仅是在某种意义上的局部最优解(是否是全局最优,需要证明)。


例题

1.田忌赛马

每个马跟比自己弱的程度最小的马

1.排序

2.蓝色最大和红色最大比较,看蓝色能不能比过红色,若比不过,拿蓝色最小的跟红色比

3.拿蓝色最大跟红色第二大的比...能比就比,不能就继续拿最差的跟最好的比


反证法上大分~事件序列问题

已知N个事件的发生时刻和结束时刻。

一些在时间上没有重叠的事件,可以构成一个事件序列,如事件{2,8,10}。

事件序列包含的事件数目,称为该事件序列的长度。

请编程找出一个最长的事件序列。

至少存在一个最长事件序列包含最早结束事件(最早结束事件是0)

反证法证明上句:

假设所有最长事件序列都不包含最早结束事件;只要证明这个假设是错的,原命题得证;

任取一个所谓的最长事件序列,把第一个事件去掉,换掉事件0,肯定跟后面都不冲突(因为换上的是最早结束的时间,原来都不冲突,现在更不冲突)

证明完后选中最早结束事件0   后面我做类似的:每次找一个最早结束的事件,只要和前面的不冲突的都选中;


2.搬桌子

一个公司要做调整搬桌子,房间有400个,一边是单号,一边双号;

走廊很窄,只通过1个桌子过;

输入:

第二行:趟数

第三行:房间号:10号搬到20号

每趟搬要10min:不重叠可以同时搬,要10min;重叠要分开搬

法一:与上题的思想差不多,只不过,改成了最早开始事件(找开始最早的)

法二:统计每个区间在时间轴上的重叠次数,并找出最大重叠次数的区间。

#include <bits/stdc++.h>
using namespace std;int main() {int t, i, j, N, P[200];  // t是测试用例的数量,N是每个测试用例的区间数量int s, d, temp, k, MAX;  // s和d是区间的起点和终点,MAX用于记录最大重叠次数cin >> t;for (i = 0; i < t; i++) {// 初始化P数组,用于记录每个时间点的重叠次数for (j = 0; j < 200; j++)P[j] = 0;cin >> N;  // 读取当前测试用例的区间数量for (j = 0; j < N; j++) {cin >> s >> d;  // 读取区间的起点和终点s = (s - 1) / 2;  // 将起点转换为数组索引d = (d - 1) / 2;  // 将终点转换为数组索引// 如果起点大于终点,交换它们if (s > d) {temp = s;s = d;d = temp;}// 在区间[s, d]内的每个时间点增加计数for (k = s; k <= d; k++)P[k]++;}// 找到最大重叠次数MAX = -1;for (j = 0; j < 200; j++)if (P[j] > MAX)MAX = P[j];// 输出最大重叠次数乘以10cout << MAX * 10 << endl;}return 0;
}

3.删数问题

已知一个长度不超过240位的正整数n(其中不含有效字0),去掉其中任意s(s小于n的长度)个数字后,将剩下的数字按原来的左右次序组成一个新的正整数。

给定n和s,请编程输出最小的新正整数。

Sample Input
178543 4
Sample Output
13

法一:从左到右扫描逆序对,删掉左边的数,若没有逆序对,删掉最后一位数

1 7 84 3 —— 1 7 5 4 3 ——1 5 4 3 ——1 4 3 —— 1 3 

1 2 3


4.青蛙的邻居

每个湖泊都有一个青蛙,如果两个湖泊之间有水渠相连,我们认为两个青蛙他们为邻居;

问:你可以画出这个湖泊分布图吗?

Sample Input

3

7 —— 青蛙个数

4 3 1 5 4 2 1 —— 第一个青蛙有4个邻居;第二个青蛙有3个邻居....

6

4 3 1 4 2 0

6

2 3 1 1 2 1 

Sample Output

YES

NO

YES

 用以下知识可解决:


离散数学:可图性判定 

两个概念:

1.度序列:若把图A所有顶点的度数排成一个序列S,则称S为图A的度序列。

度:一个顶点他有几条边,度就是几

图A

2 3 1 1 1 就是度序列

2.序列是可图的:一个非负整数组成的有限序列如果是某个无向图的度序列,则称该序列是可图的。

若度序列2 3 1 1 1可以画出图A,就是可图的;


Havel-Hakimi定理:解决可读性判定

之后再排序:3 2 2 2 1

做一趟,排序一次;只要出现负数,就不可能了,图画不出来;最后全变成0,可以画;

Havel定理的解释——加加减减与图的对应关系_哔哩哔哩_bilibili


特别说明

若要用贪心算法求解某问题的整体最优解,必须首先证明贪心思想在该问题的应用结果就是最优解!!

在使用贪心算法解决问题时,必须首先证明贪心策略能够导致整体最优解。贪心算法通常通过每一步选择局部最优解来构建全局解,但并非所有问题都适合使用贪心算法,因此证明其正确性是关键。

说明理由:

若某货币系统有三种币值,分别为一角、五分和一分;要找1角5分
求最小找币数时,是否可以用贪心法求解?

可以;先用最大的能找几个找几个;

如果将这三种币值改为一种一分、五分和一分;要找1角5分

是否还可以使用贪心法求解?

不行;

因为他不成倍数;

贪心算法的常见操作:

贪心总是要找最大的、最小的、最划算的,往往要排序;

相关文章:

贪心算法

int a[1000], b5, c8; swap(b, c); // 交换操作 memset(a, 0, sizeof(a)); // 初始化为0或-1 引导问题 为一个小老鼠准备了M磅的猫粮&#xff0c;准备去和看守仓库的猫做交易&#xff0c;因为仓库里有小老鼠喜欢吃的五香豆&#xff0c;第i个房间有J[i] 磅的五香豆&#xf…...

Linux下安装中文输入法总结

Linux下安装中文输入法总结_linux 微软拼音-CSDN博客文章浏览阅读4.2w次&#xff0c;点赞21次&#xff0c;收藏92次。众所周知&#xff0c;fcitx和ibus是两款很好用的Linux中文输入法框架。下面来说一下其安装方法以及会踩的坑。首先fcitx和ibus是不能共存的&#xff0c;两者只…...

人工智能(AI):科技新纪元的领航者

摘要 人工智能&#xff08;AI&#xff09;作为当今科技领域最具变革性的力量之一&#xff0c;正以惊人的速度重塑着我们的世界。本文旨在全面且专业地介绍人工智能&#xff0c;涵盖其定义、发展历程、关键技术、应用领域、面临的挑战以及未来展望等方面&#xff0c;以期为读者…...

c3p0、Druid连接池+工具类 Apache-DbUtils (详解!!!)

数据库连接池是在应用程序启动时创建一定数量的数据库连接&#xff0c;并将这些连接存储在池中。当应用程序需要与数据库通信时&#xff0c;它可以向池中请求一个连接&#xff0c;使用完后将连接归还给池&#xff0c;而不是关闭连接。这样可以减少创建和关闭连接的开销&#xf…...

鸿蒙开发深入浅出03(封装通用LazyForEach实现懒加载)

鸿蒙开发深入浅出03&#xff08;封装通用LazyForEach实现懒加载&#xff09; 1、效果展示2、ets/models/BasicDataSource.ets3、ets/models/HomeData.ets4、ets/api/home.ets5、ets/pages/Home.ets6、ets/views/Home/SwiperLayout.ets7、后端代码 1、效果展示 2、ets/models/Ba…...

AWS - Redshift - 外部表读取 Parquet 文件中 timestamp 类型的数据

问题&#xff1a; 通过 Redshift Spectrum 功能可以读取 S3 中的文件&#xff0c;当读取 Parquet 文件时&#xff0c;如果列格式设置为 timestamp&#xff0c; 通过 psql 客户端读取会出现以下错误&#xff1a; testdb# select * from myspectrum_schema_0219.test_ns; ERROR…...

Ubuntu20.04之VNC的安装使用与常见问题

Ubuntu20.04之VNC的安装与使用 安装图形桌面选择安装gnome桌面选择安装xface桌面 VNC-Server安装配置开机自启 VNC Clientroot用户无法登入问题临时方案永久方案 安装图形桌面 Ubuntu20.04主流的图形桌面有gnome和xface两种&#xff0c;两种桌面的安装方式我都会写&#xff0c…...

vue3学习3-route

创建路由器&#xff1a; 应用路由器&#xff1a; 路由展示区RouterView 和 路由跳转RouterLink&#xff1a; 路由组件&#xff08;在路由配置文件中配置的&#xff09;一般放到pages/views文件夹下 路由组件切换的时候执行的是 挂载/卸载操作 onMounted / onUnmouted 路由器两…...

C++:dfs,bfs各两则

1.木棒 167. 木棒 - AcWing题库 乔治拿来一组等长的木棒&#xff0c;将它们随机地砍断&#xff0c;使得每一节木棍的长度都不超过 5050 个长度单位。 然后他又想把这些木棍恢复到为裁截前的状态&#xff0c;但忘记了初始时有多少木棒以及木棒的初始长度。 请你设计一个程序…...

RK Android11 WiFi模组 AIC8800 驱动移植流程

RK Android WiFi模组 AIC8800 驱动移植流程 作者&#xff1a;Witheart更新时间&#xff1a;20250220 概要&#xff1a;本文介绍了基于 AIC8800D40 芯片的 WiFi6 模组 BL-M8800DS2-40 在 RK3568 平台上的驱动移植流程。主要涉及环境搭建、驱动代码分析、设备树修改、驱动编译配…...

深度学习-6.用于计算机视觉的深度学习

Deep Learning - Lecture 6 Deep Learning for Computer Vision 简介深度学习在计算机视觉领域的发展时间线 语义分割语义分割系统的类型上采样层语义分割的 SegNet 架构软件中的SegNet 架构数据标注 目标检测与识别目标检测与识别问题两阶段和一阶段目标检测与识别两阶段检测器…...

免费送源码:ava+springboot+MySQL 基于springboot 宠物医院管理系统的设计与实现 计算机毕业设计原创定制

摘 要 在当今社会&#xff0c;宠物已经成为人们生活中不可或缺的一部分&#xff0c;因此宠物健康和医疗问题也备受关注。为了更好地管理宠物医院的日常运营和提供优质的医疗服务&#xff0c;本研究设计并实现了一套基于Spring Boot框架的宠物医院管理系统。这一系统集成了多项功…...

【电机控制器】ESP32-C3语言模型——DeepSeek

【电机控制器】ESP32-C3语言模型——DeepSeek 文章目录 [TOC](文章目录) 前言一、简介二、代码三、实验结果四、参考资料总结 前言 使用工具&#xff1a; 提示&#xff1a;以下是本篇文章正文内容&#xff0c;下面案例可供参考 一、简介 二、代码 #include <Arduino.h&g…...

小型字符级语言模型的改进方向和策略

小型字符级语言模型的改进方向和策略 一、回顾小型字符级语言模型的处理流程 前文我们已经从零开始构建了一个小型字符级语言模型,那么如何改进和完善我们的模型呢?有哪些改进的方向?我们先回顾一下模型的流程: 图1 小型字符级语言模型的处理流程 (1)核心模块交互过程:…...

力扣-贪心-56 合并区间

思路 先按照左区间进行排序&#xff0c;然后初始化left和right&#xff0c;重叠时&#xff0c;更新right&#xff0c;不重叠时&#xff0c;收集区间 代码 class Solution { public:static bool cmp(vector<int> a, vector<int> b){if(a[0] b[0]){return a[1] &…...

vue 3D 翻页效果

<template><view class"swipe-container" touchstart"onTouchStart" touchmove"onTouchMove" touchend"onTouchEnd"><view class"page">初始页</view></view> </template><script&g…...

【系列专栏】银行信息系统研发外包风险管控-08

银行信息系统研发外包风险管控 在金融科技日新月异的当下&#xff0c;银行业务对信息系统的依赖程度与日俱增。为了充分利用外部专业资源&#xff0c;提升研发效率并合理控制成本&#xff0c;许多银行选择将信息系统研发外包。然而&#xff0c;这一策略在带来诸多便利的同时&a…...

[ComfyUI] 【AI】如何获得一张人物图片的优质描述

在使用ComfyUI时,获取一张人物图片的优质英文描述非常重要,尤其是在涉及图像生成、自动化标签和多模态AI任务时。以下是一个简单的流程,可以帮助你快速从一张人物图片中提取出精确且高质量的英文描述。 1. 打开 Hugging Face 网站 首先,您需要访问 Hugging Face 提供的 J…...

深度学习基础--ResNet网络的讲解,ResNet50的复现(pytorch)以及用复现的ResNet50做鸟类图像分类

&#x1f368; 本文为&#x1f517;365天深度学习训练营 中的学习记录博客&#x1f356; 原作者&#xff1a;K同学啊 前言 如果说最经典的神经网络&#xff0c;ResNet肯定是一个&#xff0c;这篇文章是本人学习ResNet的学习笔记&#xff0c;并且用pytorch复现了ResNet50&…...

stack,queue,priority_queue学习知识点

容器适配器 在c常用的容器中&#xff0c;有的是以容器迭代器为核心&#xff0c;而有的则以容器适配器为核心。较为常用的就包括queue和stack。接下来我将简单的以queue和stack的模拟实现介绍其特点。 在以下的模拟实现中&#xff0c;class Con就是我们的容器适配器&#xff0…...

React 第五十五节 Router 中 useAsyncError的使用详解

前言 useAsyncError 是 React Router v6.4 引入的一个钩子&#xff0c;用于处理异步操作&#xff08;如数据加载&#xff09;中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误&#xff1a;捕获在 loader 或 action 中发生的异步错误替…...

CTF show Web 红包题第六弹

提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框&#xff0c;很难让人不联想到SQL注入&#xff0c;但提示都说了不是SQL注入&#xff0c;所以就不往这方面想了 ​ 先查看一下网页源码&#xff0c;发现一段JavaScript代码&#xff0c;有一个关键类ctfs…...

基于Uniapp开发HarmonyOS 5.0旅游应用技术实践

一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架&#xff0c;支持"一次开发&#xff0c;多端部署"&#xff0c;可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务&#xff0c;为旅游应用带来&#xf…...

屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!

5月28日&#xff0c;中天合创屋面分布式光伏发电项目顺利并网发电&#xff0c;该项目位于内蒙古自治区鄂尔多斯市乌审旗&#xff0c;项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站&#xff0c;总装机容量为9.96MWp。 项目投运后&#xff0c;每年可节约标煤3670…...

sqlserver 根据指定字符 解析拼接字符串

DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...

2025盘古石杯决赛【手机取证】

前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来&#xff0c;实在找不到&#xff0c;希望有大佬教一下我。 还有就会议时间&#xff0c;我感觉不是图片时间&#xff0c;因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...

根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:

根据万维钢精英日课6的内容&#xff0c;使用AI&#xff08;2025&#xff09;可以参考以下方法&#xff1a; 四个洞见 模型已经比人聪明&#xff1a;以ChatGPT o3为代表的AI非常强大&#xff0c;能运用高级理论解释道理、引用最新学术论文&#xff0c;生成对顶尖科学家都有用的…...

3-11单元格区域边界定位(End属性)学习笔记

返回一个Range 对象&#xff0c;只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意&#xff1a;它移动的位置必须是相连的有内容的单元格…...

FFmpeg:Windows系统小白安装及其使用

一、安装 1.访问官网 Download FFmpeg 2.点击版本目录 3.选择版本点击安装 注意这里选择的是【release buids】&#xff0c;注意左上角标题 例如我安装在目录 F:\FFmpeg 4.解压 5.添加环境变量 把你解压后的bin目录&#xff08;即exe所在文件夹&#xff09;加入系统变量…...

日常一水C

多态 言简意赅&#xff1a;就是一个对象面对同一事件时做出的不同反应 而之前的继承中说过&#xff0c;当子类和父类的函数名相同时&#xff0c;会隐藏父类的同名函数转而调用子类的同名函数&#xff0c;如果要调用父类的同名函数&#xff0c;那么就需要对父类进行引用&#…...