阿里云建设网站买哪个服务,建设银行人力资源系统网站首页,做网站建设的方案,做爰的最好看的视频的网站CF1428E Carrots for Rabbits 题意#xff1a; 有 \(n\) 个萝卜#xff0c;每个萝卜的初始大小为 \(a_i\) 。现在要把这些萝卜切为为 \(k\) 个。吃每一个萝卜的时间为这个萝卜的大小的平方#xff0c;求吃完所有萝卜的最小时间#xff0c;即 \(\sum_{i1}^{k}{a_i^2}\) 最小… CF1428E Carrots for Rabbits 题意 有 \(n\) 个萝卜每个萝卜的初始大小为 \(a_i\) 。现在要把这些萝卜切为为 \(k\) 个。吃每一个萝卜的时间为这个萝卜的大小的平方求吃完所有萝卜的最小时间即 \(\sum_{i1}^{k}{a_i^2}\) 最小 。求出最小值 。 题解 二分是错的 。 贪心切两段是错的 。 正解 令 \(f(i,cnt)\) 为把第 \(i\) 个萝卜分为 \(cnt\) 个后吃完的最少时间则初始答案为 \(\sum_{i1}^{n}{f(i,1)}\) 。 维护一个小根堆存的值为 \(f(i,cnt)-f(i,cnt1)\) 每一次取出堆顶将堆顶的萝卜再切一段下来并塞回堆中 。 在这一次操作中答案减小了 \(f(i,cnt)-f(i,cnt1)\) 且这个值在这一次切割操作中是最优的所以答案是正确的。 以上操作进行 \(k-n\) 次 。 最终的答案为初始答案减去每一次取出堆顶后对答案减小的值。 大致代码 int n,k,a[Maxn];
ll ans;
ll f(ll sum,ll cnt)
{return (sum%cnt)*(sum/cnt1ll)*(sum/cnt1ll)(cnt-(sum%cnt))*(sum/cnt)*(sum/cnt);
}
struct Data
{ll sum,cnt;bool friend operator (Data x,Data y){return (f(x.sum,x.cnt)-f(x.sum,x.cnt1ll))(f(y.sum,y.cnt)-f(y.sum,y.cnt1ll));}
};
priority_queueData q;
// main
nrd(),krd();
for(int i1;in;i) a[i]rd(),q.push((Data){1ll*a[i],1ll}),ans1ll*a[i]*a[i];
for(int i1;ik-n;i)
{Data curq.top(); q.pop();ans-(f(cur.sum,cur.cnt)-f(cur.sum,cur.cnt1ll)),cur.cnt1ll;q.push(cur);
}
printf(%lld\n,ans);
