恭喜你看到了这篇题解,他会让你避开很多坑(新手推荐,大佬提些建议嘛)
当然,我不想让大佬像下面这道题中大佬一样。[AHOI2017/HNOI2017]大佬 - 洛谷https://www.luogu.com.cn/problem/P3724
1370:最小函数值(minval)
时间限制: 1000 ms 内存限制: 65536 KB
提交数: 5883 通过数: 2633
【题目描述】
有nn个函数,分别为F1,F2,...,FnF1,F2,...,Fn。定义Fi(x)=Aix2+Bix+Ci(x∈N∗)Fi(x)=Aix2+Bix+Ci(x∈N∗)。给定这些Ai、Bi和Ci,请求出所有函数的所有函数值中最小的mm个(如有重复的要输出多个)。
【输入】
第一行输入两个正整数nn和mm。
以下nn行每行三个正整数,其中第ii行的三个数分别位AiAi、BiBi和CiCi。输入数据保证Ai<=10,Bi<=100,Ci<=10000Ai<=10,Bi<=100,Ci<=10000。
【输出】
将这nn个函数所有可以生成的函数值排序后的前mm个元素。这mm个数应该输出到一行,用空格隔开。
【输入样例】
3 10 4 5 3 3 4 5 1 7 1
【输出样例】
9 12 12 19 25 29 31 44 45 54
【提示】
【数据规模】
n,m≤10000n,m≤10000。
原题链接:信息学奥赛一本通(C++版)在线评测系统http://ybt.ssoier.cn:8088/problem_show.php?pid=1370这道题看着那个函数的定义,我们不禁联想到二元一次方程的公式:
难道这道“堆及其应用”的题要让我们解二元一次方程?
那我们试试:设a,b,c为1,2,3
(-2±√4-12)/2=(-2±√-8)/2;
√-8是一个虚数,这里补充一点虚数的知识吧(虽然对这道题没用)
∵√-1=i
∴√-k=i*√k
嗯嗯,不扯远了,回归正题,这道题其实可以水暴力枚举过
我们只要输出m个即可,所以……
for(int i=0;i<m;i++)
{
}
实际上在这句话前面的都是废话,真正的分析马上开始
因为x的值是不变的,可以建立一个x的数组,然后……枚呗
顺便讲一下,这里要用优先队列进行自动排序,建立优先队列:
priority_queue<int,vector<int>,greater<int> > h;
然后,上暴力枚举代码(没啥好讲的了):
INT_MAX是int类型最大值
#include<bits/stdc++.h>
#include<queue>
using namespace std;
int a[10001],b[10001],c[10001],x[10001];
int n,m;
priority_queue<int,vector<int>,greater<int> > h;
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
{
cin>>a[i]>>b[i]>>c[i];
x[i]=1;
}
for(int i=0;i<m;i++)
{
int minx=INT_MAX,t;
for(int j=0;j<n;j++)
{
int ans=a[j]*x[j]*x[j]+b[j]*x[j]+c[j];
if(ans<minx)
{
minx=ans;
t=j;
}
}
cout<<minx<<" ";
x[t]++;
}
return 0;
}
八千位老祖宗惊讶的从地下钻了出来,一脸惊讶的看着你!!!
但是这是堆的题,还是用优先队列做一下吧!
前面都差不多:
#include<bits/stdc++.h>
#include<queue>
using namespace std;
priority_queue<int,vector<int>,less<int> > h;
int ans[10001],n,m;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
int a,b,c;
cin>>a>>b>>c;
for(int j=1;j<=m;j++)
{
int s=a*j*j+b*j+c;
if(i==1)
h.push(s);
}
}
return 0;
}
重复遍历,如果有更小的就把大的弹出,加入更小的:
if(s<h.top())
{
h.push(s);
h.pop();
}
else
break;
最后用一个数组存队列,输出就行了
AC代码:
#include<bits/stdc++.h>
#include<queue>
using namespace std;
priority_queue<int,vector<int>,less<int> > h;
int ans[10001],n,m;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
int a,b,c;
cin>>a>>b>>c;
for(int j=1;j<=m;j++)
{
int s=a*j*j+b*j+c;
if(i==1)
h.push(s);
else
{
if(s<h.top())
{
h.push(s);
h.pop();
}
else
break;
}
}
}
for(int i=1;i<=m;i++)
{
ans[i]=h.top();
h.pop();
}
for(int i=m;i>=1;i--)
cout<<ans[i]<<" ";
return 0;
}
制作不易,不喜勿喷。