【做题记录】CF1428E Carrots for Rabbits

题意：

有 \(n\) 个萝卜，每个萝卜的初始大小为 \(a_i\) 。现在要把这些萝卜切为为 \(k\) 个。吃每一个萝卜的时间为这个萝卜的大小的平方，求吃完所有萝卜的最小时间，即 \(\sum_{i=1}^{k}{a_i^2}\) 最小。求出最小值。

题解：

二分是错的。
贪心切两段是错的。

正解：

令 \(f(i,cnt)\) 为把第 \(i\) 个萝卜分为 \(cnt\) 个后吃完的最少时间，则初始答案为 \(\sum_{i=1}^{n}{f(i,1)}\) 。

维护一个小根堆，存的值为 \(f(i,cnt)-f(i,cnt+1)\) ，每一次取出堆顶，将堆顶的萝卜再切一段下来，并塞回堆中。

在这一次操作中，答案减小了 \(f(i,cnt)-f(i,cnt+1)\) ，且这个值在这一次切割操作中是最优的，所以答案是正确的。

以上操作进行 \(k-n\) 次。

最终的答案为初始答案减去每一次取出堆顶后对答案减小的值。

大致代码：

int n,k,a[Maxn];

ll ans;

ll f(ll sum,ll cnt)

{

	 return (sum%cnt)*(sum/cnt+1ll)*(sum/cnt+1ll)+(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.cnt+1ll))<(f(y.sum,y.cnt)-f(y.sum,y.cnt+1ll));

	 }

};

priority_queue<Data> q;

// main

n=rd(),k=rd();

for(int i=1;i<=n;i++) a[i]=rd(),q.push((Data){1ll*a[i],1ll}),ans+=1ll*a[i]*a[i];

for(int i=1;i<=k-n;i++)

{

	 Data cur=q.top(); q.pop();

	 ans-=(f(cur.sum,cur.cnt)-f(cur.sum,cur.cnt+1ll)),cur.cnt+=1ll;

	 q.push(cur);

}

printf("%lld\n",ans);

巴特西

【做题记录】CF1428E Carrots for Rabbits—堆的妙用

题意：

题解：

最新文章

热门文章