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

HBU算法设计与分析 贪心算法

1.最优会场调度

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
typedef pair<int,int> PII;
PII p[N];
priority_queue<int,vector<int>,greater<int>> q;  //最小堆 存储最早结束的会场的结束时间 
int n;
//其实这个题可以理解为同一个会场在同一个时间内只能进行一个活动 
//现在问所有活动都要正常进行 最少需要几个会场 
int main(){cin>>n;for(int i=0;i<n;i++) cin>>p[i].first>>p[i].second;sort(p,p+n);//默认按照所有活动的开始时间排序 q.push(p[0].second); //第一个活动一定不用开新会场 //贪心思想:每次直接与最早结束的会场的结束时间相比 只要能用 就用该会场 不能用就代表其他的也会场肯定不能用 直接开一个新会场for(int i=1;i<n;i++){if(!q.empty()&&p[i].first>=q.top()) q.pop();  // 如果最早结束的会场可以容纳当前活动,则复用该会场q.push(p[i].second);}cout<<q.size()<<endl;return 0;
} 

2.最优合并

#include <bits/stdc++.h>
using namespace std; 
priority_queue<int> pmax; //大根堆
priority_queue<int,vector<int>,greater<int> > pmin; //小根堆
int n,x;int getmin(){int sum=0;while(pmin.size()>1){int a=pmin.top();pmin.pop(); int b=pmin.top();pmin.pop();//贪心思想:每次取出堆中的两个值 根据堆的性质 取出的值必定为最小的两个值sum+=a+b;pmin.push(a+b); //计算结果再加入堆中}return sum;
}
int getmax(){int sum=0; //与小根堆计算思想相同while(pmax.size()>1){int a=pmax.top();pmax.pop();int b=pmax.top();pmax.pop();sum+=a+b;pmax.push(a+b);}return sum;
}int main(){cin>>n;for(int i=0;i<n;i++){cin>>x;pmin.push(x); //将每个值都在两个堆中各入堆一次pmax.push(x);}cout<<getmax()<<" "<<getmin()<<endl;return 0;
}

3.程序存储问题

#include <iostream>
#include <algorithm>
using namespace std;
int n,m,sum,cnt,a[100005];
int main() {cin>>n>>m;for(int i=0;i<n;i++) cin>>a[i];sort(a,a+n);//贪心思想:只要还没达到临界值 就一直加 达到就直接break掉 程序结束for(int i=0;i<n;i++){sum+=a[i];if(sum<=m) cnt++; else break;}cout<<cnt<<endl;return 0;
}

4.最优服务次序问题

#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e5+5;
typedef long long LL;
int n,a[N];
int main(){cin>>n;for(int i=0;i<n;i++) cin>>a[i];sort(a,a+n);//贪心思想:后面的每一个人都要把他排在他前面的所有时间各等一遍 所以前面的人越短越好 所以直接让每个位置都取 能取到的最短 即直接升序排序LL time=0;for(int i=0;i<n;i++) time+=(n-i)*(LL)a[i]; //每一个时间被等待了n-i次double res=time/(double)n;printf("%.2lf",res);return 0;
}

5.汽车加油问题

#include <iostream>
using namespace std;
const int N=1e5+5;
int n,k,sum,cnt,a[N];
int main(){cin>>n>>k;for(int i=0;i<=k;i++) {cin>>a[i];if(a[i]>=n){cout<<"No Solution";return 0;}}for(int i=0;i<=k;i++){if(sum+a[i]>n){ //贪心思想:尽可能多走 直到无法走 就选择加油cnt++;sum=0;}sum+=a[i];}cout<<cnt;return 0;
}

6.最优分解问题

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int n,index,a[100001];
//解题关键点为要是自然数乘积最大 应使其2 3 5 7 小数尽可能多
//eg 5=2+3 但x*5一定小于x*2*3   即若a+b=定值,a-b的绝对值越小,ab值越大 
//所以只需要尽可能找能除尽的小数即可 vector<int> res={1}; //高精度模板 
vector<int> mul(vector<int> A,int b){vector<int> C;int t=0;for(int i=0;i<A.size()||t;i++){if(i<A.size()) t+=A[i]*b;C.push_back(t%10);t/=10;}while(C.size()>1&&C.back()==0) C.pop_back();return C;
}int main(){cin>>n;//初始化第一次分解 //只要n>3 结果中就一定会有2 a[index++]=2;n-=2; //利用循环分解掉nint i=3;while(n>a[index-1]){a[index]=i++;n-=a[index];index++;} //贪心思想:尽量取小值 在不重复的情况下 尽量把多出来的值 分配给尽可能多的数//将剩下的部分x 分为x个一(因为平均分配给每一个比直接分配个某个数+x 要大 上面已证明过) //从大的数开始加 因为从小数开始会重复 for (int i=index-1;n>0;i--) {a[i]++;if(i==0) i=index; // 循环分配n--;}//后几组测试数据位数过大 所以使用高精度转换for(int i=0;i<index;i++)  res=mul(res,a[i]); for(int i=res.size()-1;i>=0;i--) cout<<res[i];return 0;
} 

相关文章:

HBU算法设计与分析 贪心算法

1.最优会场调度 #include <bits/stdc.h> using namespace std; const int N1e55; typedef pair<int,int> PII; PII p[N]; priority_queue<int,vector<int>,greater<int>> q; //最小堆 存储最早结束的会场的结束时间 int n; //其实这个题可以理…...

python pycharm安装教程及基本使用,超详细

一.PyCharm下载及安装 1.1 进入pycharm官网&#xff0c;点击下载,下载社区版本&#xff08;日常学习使用够用了&#xff09;&#xff0c;专业版是收费的哦&#xff08;功能更强大&#xff09; Download PyCharm: The Python IDE for data science and web development by Jet…...

变量提升函数提升

示例 1&#xff1a;变量提升 原始代码&#xff1a; console.log(x); // 输出: undefined var x 5; console.log(x); // 输出: 5提升后的代码&#xff08;理解为&#xff09;&#xff1a; var x; // 变量声明被提升 console.log(x); // 输出: undefined x 5; // 赋值 conso…...

el-table vue3统计计算数字

固定合计在最下列 父组件 <template><el-tablev-loading"loading"tooltip-effect"light":data"list"style"width: 100%":max-height"maxHeight"element-loading-text"拼命加载中...":header-cell-styl…...

IDE应当具备的功能

IDE 是辅助编程的工具&#xff0c;应当具备以下功能 语法高亮 显示注释 显示光键词 显示括号 matlab 自带的 IDE 没有这个功能 显示缩进 matlab 自带的 IDE 没有这个功能 显示字符串 显示数字常量 定位到函数的定义位置 Matlab 自带的集成开发环境&#xff08;IDE&am…...

Stable Diffusion初步见解(二)

Stable Diffusion 是一种先进的深度学习模型&#xff0c;用于生成高质量的图像和艺术作品。它基于扩散模型&#xff08;Diffusion Models&#xff09;&#xff0c;并结合了潜在扩散模型&#xff08;Latent Diffusion Models&#xff09;以及条件生成技术&#xff08;如文本到图…...

前端框架 react 性能优化

目录 一、不使用任何性能优化API进行优化 二、通过性能优化API优化 1、React.memo 2、useCallback 3、useMemo 4、PureComponent 三、总结​ 总览&#xff1a;react的优化核心思想就是让react跳过重新渲染那个些没有改变的Component&#xff0c;而只重新渲染发生变化的C…...

RK3568平台开发系列讲解(Input子系统篇)输入子系统介绍

🚀返回专栏总目录 文章目录 一、什么是输入子系统?二、输入设备和节点的关系沉淀、分享、成长,让自己和他人都能有所收获!😄 一、什么是输入子系统? 在 Linux 中,input 子系统是专门为处理输入类设备而设计的一个子系统或框架。它提供 了一套通用的接口和机制,用于驱…...

准备阶段 Profiler性能分析工具的使用(一)

Unity 性能分析器 (Unity Profiler) 性能分析器记录应用程序性能的多个方面并显示相关信息。使用此信息可以做出有关应用程序中可能需要优化的事项的明智决策&#xff0c;并确认所做的优化是否产生预期结果。 默认情况下&#xff0c;性能分析器记录并保留游戏的最后 300 帧&a…...

go-rod vs Selenium:自动化测试工具的比较与选择

自动化测试是软件开发过程中的关键环节&#xff0c;它能够帮助我们发现缺陷、验证功能并提高软件质量。随着Web技术的快速发展&#xff0c;市场上出现了多种自动化测试工具&#xff0c;其中Selenium和go-rod是两个备受关注的选择。本文将从多个维度对这两个工具进行比较&#x…...

探索免费的Figma中文版:开启高效设计之旅

在当今数字化设计的浪潮中&#xff0c;Figma以其强大的云端协作功能和出色的设计能力&#xff0c;成为了众多设计师的心头好。而对于国内的设计师来说&#xff0c;能够免费使用Figma中文版更是一大福音&#xff0c;下面就来一起探索一下吧。 一、Figma中文版的获取途径 虽然F…...

功能齐全,支持协作 | Docker部署一款支持多人共享的私密浏览器『n.eko』

功能齐全&#xff0c;支持协作 | Docker部署一款支持多人共享的私密浏览器『n.eko』 哈喽小伙伴们好&#xff0c;我是Stark-C~ 玩NAS的朋友基本都会在本地部署一款浏览器用来远程访问内网的网络设备&#xff0c;或者偶尔拿来浏览一些私密网站都是很方便的。 今天为大家分享的…...

部署实战(二)--修改jar中的文件并重新打包成jar文件

一.jar文件 JAR 文件就是 Java Archive &#xff08; Java 档案文件&#xff09;&#xff0c;它是 Java 的一种文档格式JAR 文件与 ZIP 文件唯一的区别就是在 JAR 文件的内容中&#xff0c;多出了一个META-INF/MANIFEST.MF 文件META-INF/MANIFEST.MF 文件在生成 JAR 文件的时候…...

Ubuntu24.04——软件包系统已损坏

如果你在使用 Ubuntu 时遇到“软件包系统已损坏”的问题&#xff0c;可以尝试以下步骤来修复它&#xff1a; 更新软件包列表&#xff1a; 打开终端&#xff0c;运行以下命令以更新软件包列表&#xff1a; sudo apt update修复损坏的软件包&#xff1a; 运行以下命令来修复损坏的…...

2024年华为OD机试真题-空栈压数-C++-OD统一考试(E卷)

最新华为OD机试考点合集:华为OD机试2024年真题题库(E卷+D卷+C卷)_华为od机试题库-CSDN博客 每一题都含有详细的解题思路和代码注释,精编c++、JAVA、Python三种语言解法。帮助每一位考生轻松、高效刷题。订阅后永久可看,发现新题及时跟新。 题目描述: 向一个空栈压入…...

嵌入式Linux基于IMX6ULL tslib学习总结

目录 1. tslib开源库介绍1.1 tslib主要功能1.2 架构 2. tslib代码简单分析2.1 ts_print_mt.c分析代码2.2 ts_setup代码分析2.3 ts_open代码分析2.4 ts_config代码分析2.5 ts_read_mt代码分析2.6 tslib中4个模块的含义 3. 使用tslib库打印触摸屏2点之间的距离 基于韦东山IMX6ULL…...

go中的参数传递是值传递还是引用传递?

在Go语言中&#xff0c;参数传递机制是一个重要的概念&#xff0c;它决定了函数内部对参数的修改是否会影响到原始数据。关于Go中的参数传递是值传递还是引用传递的问题&#xff0c;可以从以下几个方面进行解答。 一、值传递与引用传递的定义 值传递&#xff1a;在值传递中&a…...

记录一种在内核空间向用户空间通知中断的方法

记录一种在内核空间向用户空间通知中断的方法 0.前言1.代码实现1)内核设备驱动实现2)消息通知实现3)测试程序 2.解析 参考文章&#xff1a;Linux驱动实践&#xff1a;中断处理函数如何【发送信号】给应用层&#xff1f; 0.前言 最近在项目中遇到一个需求&#xff0c;需要将一个…...

.NetCore 过滤器和拦截器 的区别

Asp.NET Core 中的过滤器&#xff08;Filter&#xff09;和拦截器&#xff08;Interceptor&#xff09;是两个不同的概念&#xff0c;但它们在某些方面有相似之处&#xff0c;也有明显的区别。 &#x1f511;过滤器&#xff08;Filter&#xff09; 过滤器是Asp.NET Core中用于…...

【笔记】自动驾驶预测与决策规划_Part7_数据驱动的预测方法

文章目录 0. 前言1. 多模态传感器的编码方式1.1 栅格化表示1.2 向量化表示 Vectornet1.3 基于点云或者多模态输入的预测1.4 基于Transformer的方法 2. 网络输出的表达形式2.1 多模态轨迹回归2.2 轨迹分类2.3 轨迹回归轨迹分类2.4 目标点预测 3.场景级别的预测和决策3.1 论文&am…...

SpringBoot-17-MyBatis动态SQL标签之常用标签

文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...

C++:std::is_convertible

C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...

MODBUS TCP转CANopen 技术赋能高效协同作业

在现代工业自动化领域&#xff0c;MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步&#xff0c;这两种通讯协议也正在被逐步融合&#xff0c;形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3

一&#xff0c;概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本&#xff1a;2014.07&#xff1b; Kernel版本&#xff1a;Linux-3.10&#xff1b; 二&#xff0c;Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01)&#xff0c;并让boo…...

Android第十三次面试总结(四大 组件基础)

Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成&#xff0c;用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机&#xff1a; ​onCreate()​​ ​调用时机​&#xff1a;Activity 首次创建时调用。​…...

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

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

git: early EOF

macOS报错&#xff1a; Initialized empty Git repository in /usr/local/Homebrew/Library/Taps/homebrew/homebrew-core/.git/ remote: Enumerating objects: 2691797, done. remote: Counting objects: 100% (1760/1760), done. remote: Compressing objects: 100% (636/636…...

[USACO23FEB] Bakery S

题目描述 Bessie 开了一家面包店! 在她的面包店里&#xff0c;Bessie 有一个烤箱&#xff0c;可以在 t C t_C tC​ 的时间内生产一块饼干或在 t M t_M tM​ 单位时间内生产一块松糕。 ( 1 ≤ t C , t M ≤ 10 9 ) (1 \le t_C,t_M \le 10^9) (1≤tC​,tM​≤109)。由于空间…...

CppCon 2015 学习:Time Programming Fundamentals

Civil Time 公历时间 特点&#xff1a; 共 6 个字段&#xff1a; Year&#xff08;年&#xff09;Month&#xff08;月&#xff09;Day&#xff08;日&#xff09;Hour&#xff08;小时&#xff09;Minute&#xff08;分钟&#xff09;Second&#xff08;秒&#xff09; 表示…...

大数据治理的常见方式

大数据治理的常见方式 大数据治理是确保数据质量、安全性和可用性的系统性方法&#xff0c;以下是几种常见的治理方式&#xff1a; 1. 数据质量管理 核心方法&#xff1a; 数据校验&#xff1a;建立数据校验规则&#xff08;格式、范围、一致性等&#xff09;数据清洗&…...