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官网,点击下载,下载社区版本(日常学习使用够用了),专业版是收费的哦(功能更强大) Download PyCharm: The Python IDE for data science and web development by Jet…...
变量提升函数提升
示例 1:变量提升 原始代码: console.log(x); // 输出: undefined var x 5; console.log(x); // 输出: 5提升后的代码(理解为): 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 是辅助编程的工具,应当具备以下功能 语法高亮 显示注释 显示光键词 显示括号 matlab 自带的 IDE 没有这个功能 显示缩进 matlab 自带的 IDE 没有这个功能 显示字符串 显示数字常量 定位到函数的定义位置 Matlab 自带的集成开发环境(IDE&am…...
Stable Diffusion初步见解(二)
Stable Diffusion 是一种先进的深度学习模型,用于生成高质量的图像和艺术作品。它基于扩散模型(Diffusion Models),并结合了潜在扩散模型(Latent Diffusion Models)以及条件生成技术(如文本到图…...
前端框架 react 性能优化
目录 一、不使用任何性能优化API进行优化 二、通过性能优化API优化 1、React.memo 2、useCallback 3、useMemo 4、PureComponent 三、总结 总览:react的优化核心思想就是让react跳过重新渲染那个些没有改变的Component,而只重新渲染发生变化的C…...
RK3568平台开发系列讲解(Input子系统篇)输入子系统介绍
🚀返回专栏总目录 文章目录 一、什么是输入子系统?二、输入设备和节点的关系沉淀、分享、成长,让自己和他人都能有所收获!😄 一、什么是输入子系统? 在 Linux 中,input 子系统是专门为处理输入类设备而设计的一个子系统或框架。它提供 了一套通用的接口和机制,用于驱…...
准备阶段 Profiler性能分析工具的使用(一)
Unity 性能分析器 (Unity Profiler) 性能分析器记录应用程序性能的多个方面并显示相关信息。使用此信息可以做出有关应用程序中可能需要优化的事项的明智决策,并确认所做的优化是否产生预期结果。 默认情况下,性能分析器记录并保留游戏的最后 300 帧&a…...
go-rod vs Selenium:自动化测试工具的比较与选择
自动化测试是软件开发过程中的关键环节,它能够帮助我们发现缺陷、验证功能并提高软件质量。随着Web技术的快速发展,市场上出现了多种自动化测试工具,其中Selenium和go-rod是两个备受关注的选择。本文将从多个维度对这两个工具进行比较&#x…...
探索免费的Figma中文版:开启高效设计之旅
在当今数字化设计的浪潮中,Figma以其强大的云端协作功能和出色的设计能力,成为了众多设计师的心头好。而对于国内的设计师来说,能够免费使用Figma中文版更是一大福音,下面就来一起探索一下吧。 一、Figma中文版的获取途径 虽然F…...
功能齐全,支持协作 | Docker部署一款支持多人共享的私密浏览器『n.eko』
功能齐全,支持协作 | Docker部署一款支持多人共享的私密浏览器『n.eko』 哈喽小伙伴们好,我是Stark-C~ 玩NAS的朋友基本都会在本地部署一款浏览器用来远程访问内网的网络设备,或者偶尔拿来浏览一些私密网站都是很方便的。 今天为大家分享的…...
部署实战(二)--修改jar中的文件并重新打包成jar文件
一.jar文件 JAR 文件就是 Java Archive ( Java 档案文件),它是 Java 的一种文档格式JAR 文件与 ZIP 文件唯一的区别就是在 JAR 文件的内容中,多出了一个META-INF/MANIFEST.MF 文件META-INF/MANIFEST.MF 文件在生成 JAR 文件的时候…...
Ubuntu24.04——软件包系统已损坏
如果你在使用 Ubuntu 时遇到“软件包系统已损坏”的问题,可以尝试以下步骤来修复它: 更新软件包列表: 打开终端,运行以下命令以更新软件包列表: sudo apt update修复损坏的软件包: 运行以下命令来修复损坏的…...
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语言中,参数传递机制是一个重要的概念,它决定了函数内部对参数的修改是否会影响到原始数据。关于Go中的参数传递是值传递还是引用传递的问题,可以从以下几个方面进行解答。 一、值传递与引用传递的定义 值传递:在值传递中&a…...
记录一种在内核空间向用户空间通知中断的方法
记录一种在内核空间向用户空间通知中断的方法 0.前言1.代码实现1)内核设备驱动实现2)消息通知实现3)测试程序 2.解析 参考文章:Linux驱动实践:中断处理函数如何【发送信号】给应用层? 0.前言 最近在项目中遇到一个需求,需要将一个…...
.NetCore 过滤器和拦截器 的区别
Asp.NET Core 中的过滤器(Filter)和拦截器(Interceptor)是两个不同的概念,但它们在某些方面有相似之处,也有明显的区别。 🔑过滤器(Filter) 过滤器是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…...
云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?
大家好,欢迎来到《云原生核心技术》系列的第七篇! 在上一篇,我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在,我们就像一个拥有了一块崭新数字土地的农场主,是时…...
DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径
目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...
rknn优化教程(二)
文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK,开始写第二篇的内容了。这篇博客主要能写一下: 如何给一些三方库按照xmake方式进行封装,供调用如何按…...
Unity3D中Gfx.WaitForPresent优化方案
前言 在Unity中,Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染(即CPU被阻塞),这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案: 对惹,这里有一个游戏开发交流小组&…...
三维GIS开发cesium智慧地铁教程(5)Cesium相机控制
一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点: 路径验证:确保相对路径.…...
django filter 统计数量 按属性去重
在Django中,如果你想要根据某个属性对查询集进行去重并统计数量,你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求: 方法1:使用annotate()和Count 假设你有一个模型Item,并且你想…...
什么是库存周转?如何用进销存系统提高库存周转率?
你可能听说过这样一句话: “利润不是赚出来的,是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业,很多企业看着销售不错,账上却没钱、利润也不见了,一翻库存才发现: 一堆卖不动的旧货…...
Python爬虫(一):爬虫伪装
一、网站防爬机制概述 在当今互联网环境中,具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类: 身份验证机制:直接将未经授权的爬虫阻挡在外反爬技术体系:通过各种技术手段增加爬虫获取数据的难度…...
Ascend NPU上适配Step-Audio模型
1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统,支持多语言对话(如 中文,英文,日语),语音情感(如 开心,悲伤)&#x…...
dify打造数据可视化图表
一、概述 在日常工作和学习中,我们经常需要和数据打交道。无论是分析报告、项目展示,还是简单的数据洞察,一个清晰直观的图表,往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server,由蚂蚁集团 AntV 团队…...
