2023NOIP A层联测28-大眼鸹猫

给你两个长度为 $n$ 的序列 $a,b$，这两个序列都是单调不降的。

你可以对 $a$ 进行不超过 $m$ 次操作，每次操作你可以选择一个 $i$ 满足 $1\le i\le n$，然后选择一个整数（可以是负数）$x$，将 $a_i$ 加上 $x$，这一次操作需要花费 $x^2$ 的代价。

在做操作的过程中，你需要保证 $a$ 始终单调不降。

最后，你需要将 $a$ 序列变成 $b$ 序列，即对任意 $i$ 满足 $1\le i\le n$，都有 $a_i=b_i$。

求最小需要花费的总代价之和。

$n,m\le 10^5$

---

首先如果 $m$ 小于 $a_i\ne b_i$ 的个数，就是无解了。

操作过程中，要保证 $a$ 始终单调不降，看上去很难满足，但结论是一定存在一种合法操作方案。可以考虑一个极大的区间 $[l,r]$，$\forall i\in [l,r],a_i<b_i$，此时就从 $r$ 操作到 $l$，若 $\forall i\in [l,r],a_i>b_i$，就从 $l$ 操作到 $r$。

所以单独考虑每一个数 $|a_i-b_i|$，分配了 $x_i$ 次操作，显然每次操作将 $|a_i-b_i|$ 减少 $\frac{|a_i-b_i|}{x_i}$ 是代价最小的。设 $f(x)$ 表示给 $|a_i-b_i|$ 分配了 $x$ 次操作的最小代价，发现 $f(x)$ 是下凸函数，意思是随着 $x$ 的增大，$f(x)$ 减小的幅度越来越小。

那么我们可以先给每个数分配一次操作，对于剩下的操作用大根堆维护每个数再分配一次操作减少的代价，每次就贪心的去选代价减少得最多的，然后给它分配一次操作再放进堆里。最后把堆里的数拿出来算答案即可。

时间复杂度 $O(m\log n)$。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
constexpr int N=1e5+1;
constexpr ll mod=998244353;
int n,m;
ll a[N],b[N],dis[N],ans;
inline ll getval(ll x,ll n)
{return (x/n)*(x/n)*(n-x%n)+(x/n+1)*(x/n+1)*(x%n);
}
struct node
{int num,id;bool operator<(const node &a)const{return getval(dis[id],num)-getval(dis[id],num+1)<getval(dis[a.id],a.num)-getval(dis[a.id],a.num+1);}
};
priority_queue<node> q;
int main()
{freopen("attend.in","r",stdin);freopen("attend.out","w",stdout);cin.tie(0)->sync_with_stdio(0);cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++) cin>>b[i];int fl=0;for(int i=1;i<=n;i++) fl+=(a[i]!=b[i]);if(fl>m) cout<<"-1",exit(0);for(int i=1;i<=n;i++){if(a[i]==b[i]) continue;dis[i]=abs(a[i]-b[i]);q.push({1,i});}if(q.empty()) cout<<0,exit(0);m-=fl;while(m--){node now=q.top();q.pop();now.num++;q.push(now);}while(q.size()){ans=(ans+getval(dis[q.top().id],q.top().num))%mod;q.pop();}cout<<ans;
}