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

蓝桥杯备考:堆算法之最小函数值

这道题暴力解法就是把所有函数的前m个值代入算出来,然后把每个前m值的数组都合并起来,前m个就是我们的结果,当然这种做法是会超时的

所以我们应该选择 优先级队列,我们代入1把所有的值加入优先级队列,每次输出最小值,并且把该序列的第二个数代入进去加进队列,直到输出m个数结束

#include <iostream>
#include <queue>
using namespace std;
const int N = 1e5+10;
typedef long long ll;
ll a[N],b[N],c[N];
ll n,m;
ll calc(ll pos,ll num)
{
	return a[pos]*num*num+b[pos]*num+c[pos]; 
}
struct node{
	ll sum;//函数值 
	ll pos;//第i个函数 
	ll  num;//代入值 
	bool operator< (const node& x) const
	{
		return sum > x.sum;
	}
};
priority_queue<node> heap;
int main()
{
	cin >> n >> m;
	for(int i = 1;i<=n;i++)
	{
		cin >> a[i] >> b[i] >> c[i];
		heap.push({calc(i,1),i,1});
	}
	
	for(int i = 1;i<=m;i++)
	{
		node t = heap.top();heap.pop();
		ll sum = t.sum;ll num = t.num; ll pos = t.pos;
		cout << sum << " ";
		heap.push({calc(pos,num+1),pos,num+1});
	}
	
	
	
	
	
	return 0;
}


http://www.kler.cn/a/587513.html

相关文章:

  • Python开发合并多个PDF文件
  • 系统可观测性(5)OpenTelemetry基础使用
  • 三分钟掌握视频剪辑 | 在 Rust 中优雅地集成 FFmpeg
  • JavaScript性能优化全面指南
  • pywinauto自动安装python和java
  • DaVinci Resolve(达芬奇)快捷键大全
  • MySQL中的回表是什么?
  • Gin(后端)和 Vue3(前端)中实现 Server-Sent Events(SSE)推送
  • [Jenkins] 即将关闭,剩余生成将不会被执行问题解决
  • 支付宝小程序评论提升策略:打造高互动度的用户体验
  • 【NLP】 3. Distributional Similarity in NLP(分布式相似性)
  • 责任链模式如何减少模块之间的耦合
  • starrocks批量启停脚本
  • 生成对抗网络——pytorch与paddle实现生成对抗网络
  • WordPress顶部菜单自定义的方法
  • 酒店宾馆IPTV数字电视系统:创新宾客体验,引领智慧服务新潮流
  • 【蓝桥】模拟
  • Spring Boot整合RabbitMQ极简教程
  • 【小沐学Web3D】three.js 加载三维模型(React)
  • 微信小程序wx.request接口报错(errno: 600001, errMsg: “request:fail -2:net::ERR_FAILED“)