【题解】Luogu p2085【最小函数值】

这题数据非常弱,比较像早年NOIP。

一开始是在douglas-zhou的博客上看到的这题,(话说当时学校在搞化学竞赛,我还溜出来用iPhone敲完的这一题呢)觉得蛮有意思,就试了试,然后就A了(喵喵喵?)

打了暴力。

想了想最极限的情况,n有10000,m也有10000,那么n个函数假设都能生成合法的数,那就好像已经够m个了,所有由此可以看出每个函数应该生成很少的数,一开始试了试2500,MLE,,,1500,TLE,,,那就索性1000,开了O2,居然A了,(醉了),然后大胆一点100,没开O2,300ms暴虐数据哇

#include<cstdio>
#include<vector>
#include<algorithm>

inline int f(int a,int b,int c,int x){
    return a * x * x + b * x + c;
}

int main(){
    std::vector<int> v;
    int n,m;scanf("%d %d",&n,&m);
    
    int a,b,c;
    for(int i = 0;i < n;i++){
        scanf("%d %d %d",&a,&b,&c);
        int X = (-b) / (2 * a);
        for(int j = X;j <= 100;j++){
            if(j <= 0){
                continue;
            }
            v.push_back(f(a,b,c,j));
        }
    }
    
    std::sort(v.begin(),v.end());
    
    for(int i = 0;i < m;i++){
        printf("%d ",v[i]);
    }
    
    return 0;
}

 

Douglas_Zhou