洛谷P2085 最小函数值 题解

题目链接：P2085 最小函数值

题意：

有 \(n\) 个函数，分别为 \(F_1,F_2,\dots,F_n\)。定义 \(F_i(x)=A_ix^2+B_ix+C_i(x\in\mathbb N^*)\)。给定这些 \(A_i\)、\(B_i\) 和 \(C_i\)，请求出所有函数的所有函数值中最小的 \(m\) 个（如有重复的要输出多个）。

\(1 \leq A_i\le10,~10 \le B_i\le100,~100 \le C_i\le10^4\)。

这是一篇随机化优化的奇怪题解

题面十分不清楚。所以稍微修改了一下下。

注意这里的数据范围

根据二次函数对称轴 \(x=-\dfrac{b}{2a}\)

不难发现这些函数均在 \([0,+\infty)\) 单调递增

那就很简单了，直接用个大根堆维护 \(k\) 大值的方法搞一搞就好了

然后发现时间复杂度最坏似乎 \(O(nm\log m)\)

因此我们可以用随机化乱搞一下，防止特意构造的数据 \(😎\)

时间复杂度上界其实还是 \(O(nm\log m)\)

但是实际的复杂度比这个要低一些（然而因为常数又慢了一些）

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
#include <queue>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1e4+15)

mt19937 rd(time(0));
priority_queue<int> q;
int n,m,a[N],b[N],c[N],tmp[N],ans[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    for(int i=1; i<=m; i++) 
        tmp[i]=i, q.push(INF);
    shuffle(tmp+1,tmp+1+n,rd);
    for(int i=1; i<=n; i++)
        cin >> a[tmp[i]] >> b[tmp[i]] >> c[tmp[i]];
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
        {
            int k=a[i]*j*j+b[i]*j+c[i];
            if(k<q.top()){q.pop();q.push(k);}
            else break;
        }
    
    for(int i=m; i>=1; i--)
        ans[i]=q.top(),q.pop();
    for(int i=1; i<=m; i++)
        cout << ans[i] << " \n"[i==m];
    return 0;
}