https://codeforces.com/contest/1428/problem/E
一打开榜发现E比D过得还多，就果断先写E
可以发现一个胡萝卜如果要分为num[i]段，那么肯定是平均更好，就可以轻松算出来a[i]分成Num[i]段的最小的平方和
然后我们就贪心地去选择选择哪一个胡萝卜从分成num[i]段变成num[i]+1段，他能减少的代价最大就行了
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxl=3e5+10; int n,m,k,cnt,tot,cas;ll ans; ll a[maxl]; int num[maxl]; bool vis[maxl]; char s[maxl]; typedef pair <ll,int> p; priority_queue<p> q; inline ll calc(ll x,int i) { ll d,res; d=x/i;res=x%i; return d*d*(i-res)+(d+1)*(d+1)*res; } inline void prework() { scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) scanf("%lld",&a[i]); ans=0; for(int i=1;i<=n;i++) { ans+=a[i]*a[i];num[i]=1; if(a[i]==1) q.push({0ll,i}); else q.push({calc(a[i],1)-calc(a[i],2),i}); } } inline void mainwork() { p d;int id; for(int i=n+1;i<=k;i++) { d=q.top();q.pop(); ans-=d.first;id=d.second; num[id]++; if(a[id]<=num[id]) q.push({0ll,id}); else q.push({calc(a[id],num[id])-calc(a[id],num[id]+1),id}); } } inline void print() { printf("%lld\n",ans); } int main() { int t=1; //scanf("%d",&t); for(cas=1;cas<=t;cas++) { prework(); mainwork(); print(); } return 0; }
