洛谷 P2085 最小函数值

佚名 5年前 (2019-07-30) 算法 1284人围观抢沙发百度已收录

原题链接：P2085 最小函数值

解题思路：

　我们建一个大根堆，存最小的数到第m小的数，第m小的数就理所当然的是堆顶了。

　每次我们只需要比较新加进来的数比堆顶大还是比堆顶小，如果比堆顶小，将原来的堆顶丢掉，将新的数塞进去；

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

　如若比堆顶大，根据该题题意，a>0 && b>0，函数对称轴x = −b / 2 ∗ a恒小于0，可以得出，y在x > 0时是单调递增的

　所以接下来的函数值y只会大不会小，可以直接break掉了；

　由于我们存储的时候用的是大根堆，所以记得要逆序输出，将m个数从小到大输出；

代码如下：

#include<iostream>
#include<queue>
using namespace std;
int ans[10010];
priority_queue<int, vector<int>, less<int> > q; //最大堆
int main(){
    int n, m;
    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 k = a * j * j + b * j + c;
            if(i == 1)  q.push(k);      //
            else{
                if(k < q.top()){
                    q.push(k);
                    q.pop();
                }
                else    break;
            }
        }
    }
    for(int i = 1; i <= m; i++){
        ans[i] = q.top();
        q.pop();
    }
    for(int i = m; i >= 1; i--){
        cout << ans[i] << " ";
    }
    return 0;
}