1 ~ 2 | \(\leqslant 10\) |
3 ~ 4 | \(\leqslant 100\) |
5 ~ 6 | \(\leqslant 500\) |
7 ~ 10 | \(\leqslant 5 \times 10^3\) |
11 ~ 20 | \(\leqslant 10^5\) |
思路：
先给每个函数的\(x\)赋为\(1\),再把\(f_i(x_i+1)-f_i(x_i)\)与\(i\)存入优先队列，按\(\Delta f_i\)进行\(x_i+1\)的操作\(,\)再把\(f_i(x_i+1)-f_i(x_i)\)与\(i\)塞回优先队列\(,\)重复\(m-n\)次
证明：
\(\because f^{'}_i(x)=2a_i+b_i\And a_i \geq 1\)
\(\therefore \Delta f_i\)随\(x_i+1\)操作单调增加
又\(\because\)要求\(\sum_{i=1}^nf_i(x_i)\)最小
\(\therefore\)最小的\(\Delta f_i\)一定要执行\(x_i+1\)操作
\(\mathfrak{Talk\ is\ cheap,show\ you\ the\ code.}\)
#include<cstdio>
#include<cmath>
#include<queue>
#include<iostream>
#include<algorithm>
using namespace std;
# define Type template<typename T>
# define read read1<ll>()
Type inline T read1()
{
T t=0;
char k;
bool fl=0;
do k=getchar(),(k=='-')&&(fl=1);while('0'>k||k>'9');
while('0'<=k&&k<='9')t=(t<<3)+(t<<1)+(k^'0'),k=getchar();
return fl?-t:t;
}
# define A pair<ll,int>
# define ll long long
priority_queue<A,vector<A>,greater<A> >q;
int s,nx[100001],m;
ll a[100001],b[100001],c[100001],ans;
ll f(ll x,int n){return a[n]*x*x+b[n]*x+c[n];}
int main()
{
freopen("function.in","r",stdin);
freopen("function.out","w",stdout);
s=read;m=read-s;
for(int i=0;i++^s;nx[i]=1)
{
a[i]=read,b[i]=read,c[i]=read;
q.push(A(f(2,i)-f(1,i),i));
ans+=f(1,i);
}
while(m--)
{
A tem=q.top();
q.pop();
ans+=tem.first;
++nx[tem.second];
tem.first=f(nx[tem.second]+1,tem.second)-f(nx[tem.second],tem.second);
q.push(tem);
}
printf("%lld\n",ans);
return 0;
}