首页 > 代码库 > COGS 2334. [HZOI 2016]最小函数值
COGS 2334. [HZOI 2016]最小函数值
时间限制：1 s 内存限制：128 MB
【题目描述】
有n个函数，分别为F1,F2,...,Fn。定义Fi(x)=Aix2+Bix+Ci(x∈N∗)。给定这些Ai、Bi和Ci，请求出所有函数的所有函数值中最小的m个（如有重复的要输出多个）。
【输入格式】
第一行输入两个正整数n和m。
以下n行每行三个正整数，其中第i行的三个数分别为Ai、Bi和Ci。输入数据保证Ai<=10，Bi<=100，Ci<=10000。
【输出格式】
输出将这n个函数所有可以生成的函数值排序后的前m个元素。
这m个数应该输出到一行，用空格隔开，并且最后一个数右侧也有一个空格。
【样例输入】
3 10
4 5 3
3 4 5
1 7 1
【样例输出】
9 12 12 19 25 29 31 44 45 54
【来源】
HZOI 2016
堆 优先队列
屠龙宝刀点击就送
#include <algorithm>#include <cstdio>#include <queue>using namespace std;typedef long long LL;priority_queue<LL,vector<LL>,less<LL> >q;LL n,m,ans[5000001],pos,siz;int main(){ freopen("minval.in","r",stdin); freopen("minval.out","w",stdout); scanf("%lld%lld",&n,&m); for(int x,y,z;n--;) { scanf("%d%d%d",&x,&y,&z); if(siz!=m) { LL t=1; while(siz<m) { LL s=x*t*t+y*t+z; q.push(s); t++; siz++; } } else { LL t=1; while(1) { LL s=0; s=x*t*t+y*t+z; if(s<q.top()) { q.pop(); q.push(s); } else break; t++; } } } while(!q.empty() ) { ans[pos++]=q.top(); q.pop(); } for(int i=pos-1;i>=0;i--) printf("%d ",ans[i]);}
COGS 2334. [HZOI 2016]最小函数值
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。