首页 > 代码库 > 最小函数值
最小函数值
---恢复内容开始---
有n个函数，分别为F1,F2,...,Fn。定义Fi(x)=Ai*x^2+Bi*x+Ci(x∈N+)。给定这些Ai、Bi和Ci，请求出所有函数的所有函数值中最小的m个（如有重复的要输出多个）。
INPUT:
第一行输入两个正整数n和m(1<=m,n<=10000)。
以下n行每行三个正整数，其中第i行的三个数分别位Ai、Bi和Ci。输入数据保证1<=Ai<=10，1<=Bi<=100，1<=Ci<=10 000。
3 10
4 5 3
3 4 5
1 7 1
OUTPUT:
输出将这n个函数所有可以生成的函数值排序后的前m个元素。
这m个数应该输出到一行，用空格隔开。
9 12 12 19 25 29 31 44 45 54
思路：
题目很简单。
第一反应也和简单（爆搜）：复杂度为（n*m）
把n个函数从1到的值算出来，存进优先队列。然后输出队列的前m项。但是0<m,n<10000;
数据大时就BOOM！！
正解：
开一个结构体
1 struct node2 {3 int a,b,c,x,ans;4 friend bool operator < (node n1, node n2)5 {6 return n1.ans>n2.ans;7 }8 }f[maxn];
然后，在输入时将每个函数x=1时存进f[i].ans；
然后for循环+进出队列。
核心：
1 void work2()2 {3 node t=q.top();4 t.x++;5 t.ans=work(t);6 q.pop();7 q.push(t);8 }
cpp：
1 #include<iostream> 2 #include<string> 3 #include<algorithm> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<iomanip> 8 #include<queue> 9 #include<vector>10 using namespace std;11 const int maxn=500001;12 int n,m;13 struct node14 {15 int a,b,c,x,ans;16 friend bool operator < (node n1, node n2)17 {18 return n1.ans>n2.ans;19 }20 }f[maxn];21 22 int work(node t)23 {24 return t.a*t.x*t.x+t.b*t.x+t.c;25 }26 27 priority_queue<node>q;28 29 void work2()30 {31 node t=q.top();32 t.x++;33 t.ans=work(t);34 q.pop();35 q.push(t);36 }37 38 39 int main()40 {41 /*freopen("2.in","r",stdin);42 freopen("2.out","w",stdout);*/43 //ios::sync_with_stdio(false);44 cin>>n>>m;45 for(int i=1;i<=n;i++)46 {47 cin>>f[i].a>>f[i].b>>f[i].c;48 f[i].x=1;49 f[i].ans=work(f[i]);50 }51 for(int i=1;i<=n;i++)52 q.push(f[i]);53 for(int i=1;i<=m;i++)54 {55 cout<<q.top().ans<<" ";56 work2();57 }58 cout<<endl;59 return 0;60 }
最小函数值
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。