当前位置: 首页 > 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;
} 

http://www.lryc.cn/news/490914.html

相关文章:

  • python pycharm安装教程及基本使用,超详细
  • 变量提升函数提升
  • el-table vue3统计计算数字
  • IDE应当具备的功能
  • Stable Diffusion初步见解(二)
  • 前端框架 react 性能优化
  • RK3568平台开发系列讲解(Input子系统篇)输入子系统介绍
  • 准备阶段 Profiler性能分析工具的使用(一)
  • go-rod vs Selenium:自动化测试工具的比较与选择
  • 探索免费的Figma中文版:开启高效设计之旅
  • 功能齐全,支持协作 | Docker部署一款支持多人共享的私密浏览器『n.eko』
  • 部署实战(二)--修改jar中的文件并重新打包成jar文件
  • Ubuntu24.04——软件包系统已损坏
  • 2024年华为OD机试真题-空栈压数-C++-OD统一考试(E卷)
  • 嵌入式Linux基于IMX6ULL tslib学习总结
  • go中的参数传递是值传递还是引用传递?
  • 记录一种在内核空间向用户空间通知中断的方法
  • .NetCore 过滤器和拦截器 的区别
  • 【笔记】自动驾驶预测与决策规划_Part7_数据驱动的预测方法
  • React渲染相关内容——渲染流程API、Fragment、渲染相关底层API
  • Python中dict支持多个key的方法
  • 丹摩 | 基于PyTorch的CIFAR-10图像分类实现
  • C#变量和函数如何和unity组件绑定
  • AI模型---安装cuda与cuDNN
  • 【大数据学习 | Spark-Core】Spark提交及运行流程
  • 内网渗透横向移动1
  • 现代密码学
  • Pod 动态分配存储空间实现持久化存储
  • Jackson、Gson、FastJSON三款JSON利器比拼
  • php:nginx如何配置WebSocket代理?