发布于 

【LG2085 最小函数值 题解

题目链接here

正解讲了啥我也不清楚,但是有一种神奇的解法。

核心思路

其中关键在于:

1
2
3
4
5
void work(int a,int b,int c){
for(int i=1;i<=sqrt(m)+1;i++){
q.push(a*i*i+b*i+c);
}
}

在计算中只计算m\sqrt m的范围。如果直接m的话只能勉强获得20分。

因为计算m的复杂度是Θ(nm)\Theta(nm),显然会超时。

这可能是一种投机取巧的方式,如果数据强一点一定会被卡掉,因为当二次函数的对称轴大于了m\sqrt m,最小值就一定不会在m\sqrt m的范围内了(a>0a>0的情况),a<0a<0同样成立。

建议管理员还是可以强化一下数据,hack非正解。

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
#define MAXN 200000+10
#define INF 0x3f3f3f
using namespace std;
int read(){
int x=0,f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int a[MAXN],n,m;

priority_queue <int,vector<int>,greater<int> > q;

void work(int a,int b,int c){
for(int i=1;i<=sqrt(m)+1;i++){
q.push(a*i*i+b*i+c);
}
}
int main(){
n=read();
m=read();
int a,b,c;
for(int i=1;i<=n;i++){
a=read(),b=read(),c=read();
work(a,b,c);
}
for(int i=1;i<=m;i++){
cout<<q.top()<<" ";
q.pop();
}
}