信息学奥赛一本通评测系统P1338 最小函数值(minval)

2023-10-22 16:08:28

恭喜你看到了这篇题解，他会让你避开很多坑(新手推荐，大佬提些建议嘛)

当然，我不想让大佬像下面这道题中大佬一样。[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个数应该输出到一行，用空格隔开。

【输入样例】

【输出样例】

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;
}

制作不易，不喜勿喷。

码农公寓