[luogu] P1631 序列合并 堆+单调函数性质

前言

传送门 :

思路

我们可以把 f [ i ] = b [ i ] f[i] =b[i] f[i]=b[i] 显然排序之后,是单调的

对于 f 2 [ i ] = a [ i ] + f [ j ] f_2[i] = a[i]+f[j] f2​[i]=a[i]+f[j] 显然也是单调的

得到 多个单调函数

对于这几个单调函数 : P2085 最小函数值

都可以抽象成这种问题

先对所有的函数值 取 1 1 1 然后我们在每次弹出堆的时候

我们都让他的下标 +1

CODE

struct node
{
	int l,r;
	friend bool operator  a[y.l] + b[y.r];
	}
};

int cal(int i,int k)
{
	return a[i] * k *k + b[i]*k +c[i];
}


void solve()
{
	cin>>n;
	priority_queue q ;
	
	for(int i=1;i>a[i];
	
	for(int i=1;i>b[i];
		q.push({i,1});
	}
	
	for(int i=1;i