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;
} 

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

ISAAC Gym 7. 使用箭头进行数据可视化

在这里发布一个ISAAC GYM可以使用的箭头绘制类。 gymutil默认有WireframeBoxGeometry&#xff0c;WireframeBBoxGeometry&#xff0c; WireframeSphereGeometry三个线段集生成函数&#xff0c;可以绘制盒子和球体。绘制函数分别有draw_lines和draw_line。 同理&#xff0c;使…

【计算机网络】网段划分

一、为什么有网段划分 IP地址 网络号(目标网络) 主机号(目标主机) 网络号: 保证相互连接的两个网段具有不同的标识 主机号: 同一网段内&#xff0c;主机之间具有相同的网络号&#xff0c;但是必须有不同的主机号 互联网中的每一台主机&#xff0c;都要隶属于某一个子网 -&…

机器学习周志华学习笔记-第5章<神经网络>

机器学习周志华学习笔记-第5章<神经网络> 卷王&#xff0c;请看目录 5模型的评估与选择5.1 神经元模型5.2 感知机与多层网络5.3 BP(误逆差)神经网络算法 5.4常见的神经网络5.4.1 RBF网络&#xff08;Radial Basis Function Network&#xff0c;径向基函数网络&#xff0…

MySQL数据库设计

数据库设计 数据库是用来存在数据的&#xff0c;需要设计合理的数据表来存放数据–能够完成数据的存储&#xff0c;同时能够方便的提取应该系统所需的数据 1. 数据库的设计流程 数据库是为应用系统服务的&#xff0c;数据库的数据存储也是由应用系统决定的 当我们进行应用系统开…

Spring Boot 3.x + OAuth 2.0:构建认证授权服务与资源服务器

Spring Boot 3.x OAuth 2.0&#xff1a;构建认证授权服务与资源服务器 前言 随着Spring Boot 3的发布&#xff0c;我们迎来了许多新特性和改进&#xff0c;其中包括对Spring Security和OAuth 2.0的更好支持。本文将详细介绍如何在Spring Boot 3.x版本中集成OAuth 2.0&#xf…

数据可视化复习2-绘制折线图+条形图(叠加条形图,并列条形图,水平条形图)+ 饼状图 + 直方图

目录 目录 一、绘制折线图 1.使用pyplot 2.使用numpy ​编辑 3.使用DataFrame ​编辑 二、绘制条形图&#xff08;柱状图&#xff09; 1.简单条形图 2.绘制叠加条形图 3.绘制并列条形图 4.水平条形图 ​编辑 三、绘制饼状图 四、绘制散点图和直方图 1.散点图 2…

logback 初探学习

logback 三大模块 记录器&#xff08;Logger&#xff09;、追加器&#xff08;Appender&#xff09;和布局&#xff08;Layout&#xff09; 配置文件外层最基本的标签如图示 xml中定义的就是这个三个东西下面进入学习 包引入参考springboot 官方文档 Logging :: Spring Boo…

Linux:自定义Shell

本文旨在通过自己完成一个简单的Shell来帮助理解命令行Shell这个程序。 目录 一、输出“提示” 二、获取输入 三、切割字符串 四、执行指令 1.子进程替换 2.内建指令 一、输出“提示” 这个项目基于虚拟机Ubuntu22.04.5实现。 打开终端界面如图所示。 其中。 之前&#x…

《图像梯度与常见算子全解析:原理、用法及效果展示》

简介:本文深入探讨图像梯度相关知识&#xff0c;详细介绍图像梯度是像素灰度值在不同方向的变化速度&#xff0c;并以 “pig.JPG” 图像为例&#xff0c;通过代码展示如何选取图像部分区域并分析其像素值以论证图像梯度与边缘信息的关联。接着全面阐述了 Sobel 算子&#xff0c…

项目进度计划表:详细的甘特图的制作步骤

甘特图&#xff08;Gantt chart&#xff09;&#xff0c;又称为横道图、条状图&#xff08;Bar chart&#xff09;&#xff0c;是一种用于管理时间和任务活动的工具。 甘特图由亨利劳伦斯甘特&#xff08;Henry Laurence Gantt&#xff09;发明&#xff0c;是一种通过条状图来…

A045-基于spring boot的个人博客系统的设计与实现

&#x1f64a;作者简介&#xff1a;在校研究生&#xff0c;拥有计算机专业的研究生开发团队&#xff0c;分享技术代码帮助学生学习&#xff0c;独立完成自己的网站项目。 代码可以查看文章末尾⬇️联系方式获取&#xff0c;记得注明来意哦~&#x1f339; 赠送计算机毕业设计600…

QT基础 编码问题 定时器 事件 绘图事件 keyPressEvent QT5.12.3环境 C++实现

一、编码问题 在计算机编程中&#xff0c;流&#xff08;Stream&#xff09;是一种抽象的概念&#xff0c;用于表示数据的输入或输出。根据处理数据的不同方式&#xff0c;流可以分为字节流&#xff08;Byte Stream&#xff09;和字符流&#xff08;Character Stream&#xff0…

Python爬虫项目 | 二、每日天气预报

文章目录 1.文章概要1.1 实现方法1.2 实现代码1.3 最终效果1.3.1 编辑器内打印显示效果实际应用效果 2.具体讲解2.1 使用的Python库2.2 代码说明2.2.1 获取天气预报信息2.2.2 获取当天日期信息&#xff0c;格式化输出2.2.3 调用函数&#xff0c;输出结果 2.3 过程展示 3 总结 1…

百度在下一盘大棋

这两天世界互联网大会在乌镇又召开了。 我看到一条新闻&#xff0c;今年世界互联网大会乌镇峰会发布“2024 年度中国互联网企业创新发展十大典型案例”&#xff0c;百度文心智能体平台入选。 这个智能体平台我最近也有所关注&#xff0c;接下来我就来讲讲它。 百度在下一盘大棋…

UG NX二次开发(C++)-UIStyler-指定平面的对象和参数获取

文章目录 1、前言2、在UG NX中创建平面和一个长方体,3、在UI Styler中创建一个UI界面4、在VS中创建一个工程4.1 创建并添加工程文件4.2 在Update_cb方法中添加选择平面的代码4.3 编译完成并测试效果1、前言 在采用NXOpen C++进行二次开发时,采用Menu/UIStyler是一种很常见的…

【软考】数据库

1. 数据模型 1.1 概念数据模型 概念数据模型一般用 E-R 图表示&#xff0c;常用术语如下&#xff1a; 实体&#xff1a;客观存在的事物&#xff0c;如&#xff1a;一个单位、一个职工、一个部门、一个项目。属性&#xff1a;学生实体有学号、姓名、出生日期等属性。码&#…

【强化学习的数学原理】第04课-值迭代与策略迭代-笔记

学习资料&#xff1a;bilibili 西湖大学赵世钰老师的【强化学习的数学原理】课程。链接&#xff1a;强化学习的数学原理 西湖大学 赵世钰 文章目录 一、值迭代算法二、策略迭代算法三、截断策略迭代算法四、本节课内容summary 一、值迭代算法 值迭代算法主要包括两部分。 第一…

jupyter notebook的 markdown相关技巧

目录 1 先选择为markdown类型 2 开关技巧 2.1 运行markdown 2.2 退出markdown显示效果 2.3 注意点&#xff1a;一定要 先选择为markdown类型 3 一些设置技巧 3.1 数学公式 3.2 制表 3.3 目录和列表 3.4 设置各种字体效果&#xff1a;加粗&#xff0c;斜体&#x…

Spring Boot3远程调用工具RestClient

Spring Boot3.2之后web模块提供了一个新的远程调用工具RestClient&#xff0c;它的使用比RestTemplate方便&#xff0c;开箱即用&#xff0c;不需要单独注入到容器之中&#xff0c;友好的rest风格调用。下面简单的介绍一下该工具的使用。 一、写几个rest风格测试接口 RestCont…

vscode可以编译通过c++项目,但头文件有红色波浪线的问题

1、打开 VSCode 的设置&#xff0c;可以通过快捷键 Ctrl Shift P 打开命令面板&#xff0c;然后搜索并选择 “C/C: Edit Configurations (JSON)” 命令&#xff0c;这将在 .vscode 文件夹中创建或修改 c_cpp_properties.json 文件 {"configurations": [{"name…