P2085 最小函数值 (堆)
发布时间:2020-12-14 04:47:14 所属栏目:大数据 来源:网络整理
导读:题目描述 有n个函数,分别为F1,F2,...,Fn。定义Fi(x)=Ai x^2+Bi x+Ci (x∈N*)。给定这些Ai、Bi和Ci,请求出所有函数的所有函数值中最小的m个(如有重复的要输出多个)。 输入输出格式 输入格式: 输入数据:第一行输入两个正整数n和m。以下n行每行三个正整数
题目描述有n个函数,分别为F1,F2,...,Fn。定义Fi(x)=Aix^2+Bix+Ci (x∈N*)。给定这些Ai、Bi和Ci,请求出所有函数的所有函数值中最小的m个(如有重复的要输出多个)。 输入输出格式输入格式: 输入数据:第一行输入两个正整数n和m。以下n行每行三个正整数,其中第i行的三个数分别位Ai、Bi和Ci。Ai<=10,Bi<=100,Ci<=10 000。 输出格式: 输出数据:输出将这n个函数所有可以生成的函数值排序后的前m个元素。这m个数应该输出到一行,用空格隔开。 输入输出样例输入样例#1: 3 10 输出样例#1: 9 12 12 19 25 29 31 44 45 54 说明数据规模:n,m<=10000 Solution这道题就是一个堆的裸题.
于是我便用了一个堆来实现对于函数值的处理.
于是这样即可. 代码#include<bits/stdc++.h> using namespace std; const int maxn=10008; int a[maxn],b[maxn],c[maxn]; int n,m,now,be[maxn]; priority_queue<int>q; int f(int i,int j) {return a[i]*j*j+b[i]*j+c[i];} int main() { ios::sync_with_stdio(false); cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i]>>b[i]>>c[i]; for(int j=1;j<=m;j++) for(int i=1;i<=n;i++) { if(q.size()==m)break; now=f(i,j); be[i]=j+1; q.push(now); } now=q.top(); for(int i=1;i<=n;i++) for(int j=be[i];j<=m;j++) { if(f(i,j)>now)break; q.pop(); q.push(f(i,j)); now=q.top(); } int ans[maxn]; for(int i=1;i<=m;i++) {ans[m-i+1]=q.top();q.pop();} for(int i=1;i<=m;i++) cout<<ans[i]<<' '; return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |