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

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

当然,我不想让大佬像下面这道题中大佬一样。[AHOI2017/HNOI2017]大佬 - 洛谷信息学奥赛一本通评测系统P1338 最小函数值(minval)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++版)在线评测系统信息学奥赛一本通评测系统P1338 最小函数值(minval)http://ybt.ssoier.cn:8088/problem_show.php?pid=1370这道题看着那个函数的定义,我们不禁联想到二元一次方程的公式:

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

难道这道“堆及其应用”的题要让我们解二元一次方程?

那我们试试:设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;
}

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

 

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

 八千位老祖宗惊讶的从地下钻了出来,一脸惊讶的看着你!!!

但是这是堆的题,还是用优先队列做一下吧!

前面都差不多:

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

制作不易,不喜勿喷。

上一篇:python的三个函数(eval、exec、complie)和python版RMI


下一篇:python基础三:函数