P2085 最小函数值

题目简述

对于n个函数 \(f_i(x)\) ，在 x 均为正整数情况下，求这些函数值中最小的m个

思路

大水题，裸的堆，主要记录一下重载运算符写法以及结构体套优先队列到底是怎么写的qwq

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
struct Node{
  int a,b,c;
}s[N];
struct node{
  int id,op,num,x;
  friend bool operator < (node x,node y) {
    return x.num>y.num;//按照升序排列
  }
};
priority_queue<node>q;
int main(){
  freopen("2085.in","r",stdin);
  freopen("2085.out","w",stdout);
  int n,m;
  cin>>n>>m;
  for(int i=1;i<=n;i++){
    cin>>s[i].a>>s[i].b>>s[i].c;
    int x=-(s[i].b)/(2*s[i].a);
    if(x<0){
      q.push(node{i,1,s[i].a+s[i].b+s[i].c,1});
      continue;
    }
    if(s[i].b%(2*s[i].a)==0){
      q.push(node{i,0,s[i].a*x*x+s[i].b*x+s[i].c,x});
      if(x-1>0)q.push(node{i,-1,s[i].a*(x-1)*(x-1)+s[i].b*(x-1)+s[i].c,x-1});
      q.push(node{i,1,s[i].a*(x+1)*(x+1)+s[i].b*(x+1)+s[i].c,x+1});
    }
    else {
      q.push(node{i,-1,s[i].a*x*x+s[i].b*x+s[i].c,x});
      q.push(node{i,1,s[i].a*(x+1)*(x+1)+s[i].b*(x+1)+s[i].c,x+1});
    }
  }
  int tmp=1;
  while(tmp<=m){
    int id=q.top().id,op=q.top().op,num=q.top().num,x=q.top().x;
    q.pop();
    if(x<=0)continue;
    cout<<num<<' ';
    tmp++;
    if(op==1||op==-1){
      q.push(node{id,op,s[id].a*(x+op)*(x+op)+s[id].b*(x+op)+s[id].c,x+op});
    }
  }
  return 0;
}