2023.11.10联赛 T3题解
题目大意
题目思路
感性理解一下，将一个数的平方变成多个数平方的和，为了使代价最小，这些数的大小应该尽可能的平均。
我们可以将 ∣ b i − a i ∣ |b_i-a_i| ∣bi−ai∣放入大根堆，同时将这个数划分的次数以及多划分一段减少的代价放入，按减少的代价从大到小取。
总时间复杂度为 O ( m log n ) \mathcal O(m \log n) O(mlogn)。
具体实现参考代码。
#include<bits/stdc++.h>
using namespace std;
int n,m;
long long a[100000+10];
__int128 ans=0;
struct node
{long long x,l,val;bool operator<(const node &a)const {return val<a.val;}
};
priority_queue<node> p;
const long long mod=998244353;
long long read()
{long long s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9')s=s*10+(ch-'0'),ch=getchar();return s*w;
}
long long cal(long long x,long long y)
{long long sum=0;sum=(x%y)*(x/y+1)*(x/y+1)+(y-x%y)*(x/y)*(x/y);return sum;
}
void write(long long s)
{if(s>9)write(s/10);putchar(s%10+'0');
}
int main()
{freopen("attend.in","r",stdin);freopen("attend.out","w",stdout);n=read(),m=read();for(int i=1;i<=n;++i)a[i]=read();for(int i=1;i<=n;++i){int x=read();a[i]=abs(a[i]-x);if(a[i])p.push((node){a[i],1,a[i]*a[i]-cal(a[i],2)}),ans+=a[i]*a[i];}if(p.empty()){printf("0");return 0;}if(m<p.size()){printf("-1");return 0;}m-=p.size();for(int i=1;i<=m;++i){node k=p.top();p.pop();ans-=k.val;p.push((node){k.x,k.l+1,cal(k.x,k.l+1)-cal(k.x,k.l+2)});}ans=ans%mod;write(ans);return 0;
}