【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的范围。如果直接m的话只能勉强获得20分。
因为计算m的复杂度是Θ(nm)，显然会超时。
这可能是一种投机取巧的方式，如果数据强一点一定会被卡掉，因为当二次函数的对称轴大于了m，最小值就一定不会在m的范围内了（a>0的情况），a<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();
}
}
|
